Automatic commutativity detection for generalized paxos

A computer-readable storage medium that is not a signal with computer-executable instructions stored thereon for performing a 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.

A learner comprising:

• a memory storing a transactions table;
• a processor;
• a receiver executing in the processor and configured to receive a vote for a command from one of a plurality of acceptors, wherein the vote is associated with a ballot;
• a ballot updater executing in the processor and configured to determine if the ballot associated with the vote is newer than a current ballot, and to replace 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;
• a commutativity detector executing in the processor and configured to determine if the voted for command commutes with a set of previously voted for commands from the acceptor for the current ballot, the commutativity detector comprising an executor executing in the processor and comprising a transactional substrate in a state machine, the commutativity detector configured to execute the voted for command in the transactional substrate without committing the state machine to a result of executing the voted for command and to determine a transactional state resulting from the execution of the voted for command in the transactional substrate and to store the voted for command and the resulting transactional state in the transactions table, the commutativity detector further comprising a conflict detector executing in the processor and configured to determine whether any two commands in the set of previously voted for commands perform read and write operations to a same location in the memory, the commutativity detector being further configured to add the voted for command to the set of previously voted for commands from the acceptor if the voted for command commutes with a set of previously voted for commands from the acceptor for the current ballot and, if the voted for command does not commute with the set of previously voted for commands from the acceptor for the current ballot, to append a sentinel value to the set of previously voted for commands from the acceptor for the current ballot and to add the voted for command to a buffer associated with 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;
• a quorum detector executing in the processor and configured to determine whether a quorum of the plurality of acceptors have voted for an equivalent set of commands from the set of previously voted for commands;
• a committer executing in the processor and configured to commit the state machine if it is determined that a quorum of acceptors have voted for an equivalent set of commands;
• and
• a quorum disagreement detector executing in the processor and configured to determine if there is a quorum disagreement and to:
• notify a proposer to begin a new ballot if it is determined that there is a quorum disagreement;
• 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.