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:
Jan. 21, 2003
Filed:
Sep. 23, 1999
Phillip B. Gibbons, N. Plainfield, NJ (US);
Lucent Technologies Inc., Murray Hill, NJ (US);
Abstract
There is provided methods and systems for testing linearizable, linearizable priority, and non-linearizable queues. According to one embodiment of the invention, there is provided a method for verifying correct function of a linearizable queue with respect to a program executed by a plurality of processors in a computer processing system. A distinct-values trace is given that includes operations on the queue and an identifier associated with each of the operations. Each operation is associated with two timestamps respectively corresponding to a start time and an end time of the operation. The method includes the step of matching the operations to generate corresponding operation pairs, based on the identifiers. The function of the queue is identified as correct, when, for any operation pair comprising an enqueue operation e and a corresponding dequeue operation e′, there does not exist another operation pair comprising an enqueue operation d and a corresponding dequeue operation d′ such that an end time of the enqueue operation e precedes a start time of the enqueue operation d and an end of the dequeue operation d′ precedes a start of the dequeue operation e′.