Patent ID: 8046413

Claim:
A method for commutativity detection in the generalized Paxos algorithm, the method comprising: receiving a vote for a command from one of a plurality of acceptors at a learner, wherein the learner is associated with a state machine, the command is executable by the state machine, and the vote is associated with a ballot; determining if the ballot associated with the vote is newer than a current ballot, and replacing the current ballot with the ballot associated with the vote if it is determined that the ballot associated with the vote is newer than the current ballot; determining if the voted for command commutes with a set of previously voted for commands from the acceptor for the current ballot by executing the voted for command in a transactional substrate associated with the state machine, determining a transactional state resulting from the execution of the voted for command in the transactional substrate, and storing the voted for command and the resulting transactional state in a transactions table, and if the voted for command commutes with the set of previously voted for commands from the acceptor for the current ballot, adding the voted for command to the set of previously voted for commands from the acceptor, and, if the voted for command does not commute with the set of previously voted for commands from the acceptor for the current ballot, then appending a sentinel value to the set of previously voted for commands from the acceptor for the current ballot, wherein the stored transactional state comprises a record of objects read before execution of the voted for command in the transactional substrate, a record of objects written and corresponding written values, and a record of a response sent to a client from which the voted for command originated; determining if a quorum of acceptors has voted for an equivalent set of commands from the set of previously voted for commands; committing the state machine to each command from the equivalent set of commands if it is determined that a quorum of acceptors has voted for an equivalent set of commands; if it is determined that a quorum of acceptors has not voted for a set of equivalent commands: determining if there is a quorum disagreement; and notifying a proposer to begin a new ballot if it is determined that there is a quorum disagreement.