Fast Paxos recovery

A method for resolving conflicts in a distributed computer system implementing distributed fault-tolerant consensus algorithms, the method comprising:

• performing a distributed fault-tolerant consensus process in a distributed computer system comprising a plurality of devices, wherein each device votes for proposals received directly from a client and generates vote messages used to reach consensus on said client proposals;
• each device sending the vote messages generated by that device during operation of the distributed fault-tolerant consensus process to each of other devices among the plurality of devices;
• initiating a conflict resolution process when the vote messages for at least one function received from a first quorum of devices among the plurality of devices indicate that a conflict had occurred;
• and
• performing the conflict resolution process by each of the devices using the vote messages previously sent to the devices, wherein performing the conflict resolution process comprises:
• each device independently determining a function that would have been proposed by a leader device had the leader device received the vote messages sent to that device;
• each device transmitting a subsequent vote message to a second quorum of devices among the plurality of devices, the subsequent vote message comprising the determined function and a next proposal number that is immediately subsequent to a proposal number corresponding to the vote messages;
• each device receiving subsequent vote messages from other devices among the plurality of devices;
• and
• each device determining that the determined function was selected for conflict resolution when the subsequent vote messages are received from the other devices among the plurality of devices, and the transmitted subsequent vote message comprises a quorum of subsequent vote messages.

A computer-readable storage medium having computer-executable instructions for resolving conflicts in a distributed computer system comprising a plurality of devices implementing distributed fault-tolerant consensus algorithms, wherein the computer-executable instructions are executed to perform steps comprising:

• at least one device among the plurality of devices receiving vote messages generated by each device during operation of a distributed fault-tolerant consensus process;
• initiating a conflict resolution process when the vote messages for at least one function received from a first quorum of devices among the plurality of devices indicate that a conflict had occurred;
• and
• performing the conflict resolution process by the at least one device using the vote messages previously received by the at least one device, wherein performing the conflict resolution process comprises:
• the at least one device selecting a proposed function from the at least one function voted for by the vote messages and transmitting a proposal to a second quorum of devices among the plurality of devices, the proposal comprising the proposed function and a next proposal number that is immediately subsequent to a proposal number corresponding to the vote messages;
• and
• the at least one device determining that the proposed function is selected for conflict resolution when subsequent vote messages are received in response to the transmitted proposal from a third quorum of devices among the plurality of devices.

A computer-readable storage medium having computer-readable instructions for resolving conflicts in a distributed computer system comprising a plurality of devices implementing distributed fault-tolerant consensus algorithms, wherein the computer-executable instructions are executed to perform steps comprising:

• each device among the plurality of devices receiving vote messages generated by each of other devices among the plurality of devices during operation of a distributed fault-tolerant consensus process;
• initiating a conflict resolution process when the vote messages for at least one function received from a first quorum of devices among the plurality of devices indicate that a conflict had occurred;
• and
• performing the conflict resolution process by each of the devices using the vote messages previously received by each of the devices, wherein performing the conflict resolution process comprises:
• each device independently determining a function that would have been proposed by a leader device had the leader device received the vote messages received by that device;
• each device transmitting a subsequent vote message to a second quorum of devices among the plurality of devices, the subsequent vote message comprising the determined function and a next proposal number that is immediately subsequent to a proposal number corresponding to the vote messages;
• each device receiving subsequent vote messages from other devices among the plurality of devices;
• and
• each device determining that the determined function was selected for conflict resolution when the subsequent vote messages are received from the other devices among the plurality of devices, and the transmitted subsequent vote message comprises a quorum of subsequent vote messages.

A computing device in a distributed computer system implementing distributed fault-tolerant consensus algorithms, the computing device comprising:

• a network interface performing steps comprising:
• receiving vote messages for at least one function from a first quorum of devices among a plurality of devices in the distributed computer system during operation of a distributed fault-tolerant consensus process, a conflict resolution process being initiated when the vote messages received indicate that a conflict had occurred;
• transmitting a proposal for conflict resolution to a second quorum of devices among the plurality of devices, the proposal comprising a proposed function and a next proposal number that is immediately subsequent to a proposal number corresponding to the vote messages;
• and receiving subsequent vote messages in response to the transmitted proposal;
• and
• a processing unit performing steps comprising:
• choosing the proposed function from the at least one function voted for by the vote messages;
• and determining that the proposed function was selected when the subsequent vote messages are received from a third quorum of devices among the plurality of devices.

A computing device in a distributed computer system implementing distributed fault-tolerant consensus algorithms, the computing device comprising:

• a network interface performing steps comprising:
• receiving vote messages for at least one function from a first quorum of devices among a plurality of devices in a distributed computing system during operation of a distributed fault-tolerant consensus process, a conflict resolution process being initiated when the vote messages received indicate that a conflict had occurred;
• transmitting a subsequent vote message for conflict resolution to a second quorum of devices among the plurality of devices, the subsequent vote message comprising a proposed function and a next proposal number that is immediately subsequent to a proposal number corresponding to the vote messages;
• and receiving subsequent vote messages from other devices among the plurality of devices;
• and
• a processing unit performing steps comprising:
• determining the proposed function to be that function that would have been proposed by a leader device among the plurality of devices for resolving the conflict, had the leader device received the vote messages;
• and determining that the proposed function was selected when the subsequent vote messages are received from the other devices among the plurality of devices and the transmitted subsequent vote message comprises a quorum of subsequent vote messages.