Validation of priority queue processing

• US 8,612,649 B2
• Filed: 12/17/2010
• Issued: 12/17/2013
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Cormode, Graham, Chakrabarti, Amit, Kondapally, Ranganath, McGregor, Andrew Iain Shaw
• Primary Examiner(s): Lee, Chun-Kuan
• Assistant Examiner(s): MARTINEZ, DAVID E
• Application Number:
  US12/971,913
• Publication Number:
  US 20120159500A1
• Time in Patent Office: 1,096 Days
• Field of Search: None
• US Class Current: 710/52
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

A method for validating outsourced processing of a priority queue includes configuring a verifier for independent, single-pass processing of priority queue operations that include insertion operations and extraction operations and priorities associated with each operation. The verifier may be configured to validate N operations using a memory space having a size that is proportional to the square root of N using an algorithm to buffer the operations as a series of R epochs. Extractions associated with each individual epoch may be monitored using arrays Y and Z. Insertions for the epoch k may monitored using arrays X and Z. The processing of the priority queue operations may be verified based on the equality or inequality of the arrays X, Y, and Z. Hashed values for the arrays may be used to test their equality to conserve storage requirements.

Claims

1. A method for validating a priority queue, comprising:

assigning a plurality of priority queue operations comprising insertions and extractions into a plurality of epochs, wherein each of the insertions and each of the extractions is associated with a corresponding priority;

maintaining a set of variables, including at least two variables for each of the plurality of epochs, to record information indicative of insertions and extractions assigned to corresponding epochs; and

validating correct operation of the priority queue based on the set of variables,

wherein the plurality of priority queue operations includes N operations and wherein the assigning of the plurality of priority queue operations results in R epochs wherein R is proportional to a square root of N.

2. The method of claim 1, wherein the set of variables include an array X, an array Y, and an array Z, and wherein the method includes initializing the array X, the array Y, and the array Z to zero.

3. The method of claim 2, wherein validating correct operation of the priority includes verifying equality of the array X, the array Y, and the array Z.

4. The method of claim 1, wherein assigning the plurality of priority queue operations includes:

buffering consecutive operations; and

canceling operation pairs, wherein an operation pair includes an insertion of a given priority and a subsequently occurring extraction of the given priority within the buffer.

5. The method of claim 1, wherein the assigning of the plurality of priority queue operations includes processing each of the plurality of epochs sequentially and maintaining an array indicative of a maximum priority of extractions assigned to a current epoch and to each previously processed epoch.

6. The method of claim 1, wherein hashing function representations of the set of variables are maintained and wherein a memory space required to process the plurality of priority queue operations is proportional to a number of epochs in the plurality of epochs.

7. The method of claim 6, wherein the hashing function is a linear function with respect to an input on which it operates.

8. A system for validating a priority queue, the system comprising:

a processor; and

memory storing instructions which when executed cause the processor to perform operations comprising;

assigning a plurality of priority queue operations comprising insertions and extractions into a plurality of epochs, wherein each of the insertions and each of the extractions is associated with a corresponding priority;

maintaining a set of variables, including at least two variables for each of the plurality of epochs, to record information indicative of insertions and extractions assigned to corresponding epochs; and

validating correct operation of the priority queue based on the set of variables,

wherein the plurality of priority queue operations includes N operations and wherein the assigning of the plurality of priority queue operations results in R epochs wherein R is proportional to a square root of N.

9. The computer of claim 8, wherein the set of variables includes an array X, an array Y, and an array Z, and wherein the operations include initializing the array X, the array Y, and the array Z to zero.

10. The computer of claim 9, wherein the operations further comprise verifying equality of the array X, the array Y, and the array Z.

11. The computer of claim 8, wherein the operations further comprise:

buffering consecutive operations; and

canceling operation pairs, wherein an operation pair includes an insertion of a given priority and a subsequently occurring extraction of the given priority within the buffer.

12. The computer of claim 8, wherein the operations further comprise processing each of the plurality of epochs sequentially and maintaining an array indicative of a maximum priority of extractions assigned to a current epoch and to each previously processed epoch.

13. The computer of claim 8, wherein the operations include maintaining hashing function representations of the set of variables.

14. A memory storing instructions, which when executed by a processor, cause the processor to perform operations comprising:

assigning a plurality of priority queue operations comprising insertions and extractions into a plurality of epochs, wherein each of the insertions and each of the extractions is associated with a corresponding priority;

maintaining a set of variables, including at least two variables for each of the plurality of epochs, to record information indicative of insertions and extractions assigned to corresponding epochs; and

validating correct operation of the priority queue based on the set of variables,

wherein the plurality of priority queue operations includes N operations and wherein the assigning of the plurality of priority queue operations results in R epochs wherein R is proportional to a square root of N.

15. The memory of claim 14, wherein the set of variables include an array X, an array Y, and an array Z, and wherein the operations include initializing the array X, the array Y, and the array Z to zero.

16. The memory of claim 15, wherein the operations further comprise verifying equality of the array X, the array Y, and the array Z.

17. The memory of claim 14, wherein the operations further comprise:

buffering consecutive operations; and

canceling operation pairs, wherein an operation pair includes an insertion of a given priority and a subsequently occurring extraction of the given priority within the buffer.

18. The memory of claim 14, wherein the operations further comprise processing each of the plurality of epochs sequentially and maintaining an array indicative of a maximum priority of extractions assigned to a current epoch and to each previously processed epoch.