The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Dec. 17, 2013
Filed:
Dec. 17, 2010
Graham Cormode, Morristown, NJ (US);
Amit Chakrabarti, Hanover, NH (US);
Ranganath Kondapally, Hanover, NH (US);
Andrew Iain Shaw Mcgregor, Amherst, MA (US);
Graham Cormode, Morristown, NJ (US);
Amit Chakrabarti, Hanover, NH (US);
Ranganath Kondapally, Hanover, NH (US);
Andrew Iain Shaw McGregor, Amherst, MA (US);
AT&T Intellectual Property I, L.P., Atlanta, GA (US);
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.