Patent ID: 8413122
Filing Date: 2013-04-02
Classification: G06F

Abstract:
1. A method, performed by a computing device, of verifying the correctness of an execution history that includes operations executed in parallel to a concurrent priority queue having insert and remove operations, said method comprising: defining a rule set that includes an operation rule set, that defines insert and remove operation behavior on the priority queue, a new state rule set and an obsolete state rule set; reading the execution history from a storage device; building a list of events to be processed that includes a start of insertion event, an end of insertion event, a start of removal event and an end of removal event for each operation included in the execution history, where each event includes a timestamp according to the respective start time and end time of each operation; processing each event in the list of events sequentially, according to the timestamps of each respective event; building a state set, in response to said processing, each state set having: a definite heap collection including a data set shared by all states including the elements in the priority queue; an “associated removal” list including a collection of pairs of insert and remove operations; a “pending removal” list including a collection of remove operations; a “pending insert” list including a collection of insert operations; and a “finished insertion” list including a collection of insertion operations that have succeeded; where a new state is added to the state set when processing an event creates a new state according to a new state rule included the new state rule set, and removing an obsolete state in the state set when processing an event removes an obsolete state according to a obsolete state rule included in the obsolete state rule set; and when the state set is empty, outputting a incorrect result to at least one of a storage device or a display device; wherein, when every event has been processed and the state set includes at least one state, outputting a correct result to at least one of a storage device or a display device.