VIRTUALLY SYNCHRONOUS PAXOS

• US 20090150566A1
• Filed: 12/07/2007
• Published: 06/11/2009
• Est. Priority Date: 12/07/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Malkhi, Dahlia, Lamport, Leslie B., Zhou, Lidong
• Granted Patent: US 7,849,223 B2
• Time in Patent Office: Days
• US Class Current: 709/242
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416

Abstract

A variant of Paxos is referred to as Virtually Synchronous Paxos (VS Paxos). VS Paxos is a self-reconfigurable protocol that allows for delay only for reconfiguration decisions, without placing an artificial limit on regular decisions. In an implementation of VS Paxos, subject to any restriction on reconfiguration decisions, a leader may activate an unbounded number of consensus instances ahead. A VS Paxos technique permits unlimited progress during stability periods, in that a leader may initiate commands at any number of consensus instances without bound. VS Paxos waits for command completion only when configuration-changing commands occur.

Claims

1. A method of fault tolerant state machine replication, comprising:

proposing a first update to a data state to a plurality of computing devices;

proposing at least a second update to the computing devices without waiting for a quorum of acknowledgements on the first update; and

implementing the first update if the quorum of acknowledgements on the first update is received; and

implementing the second update if a quorum of acknowledgements on the second update is received.

2. The method of claim 1, wherein each of the first update and the second update comprises an associated ballot number.

3. The method of claim 2, further comprising determining an ordering of the first update and the second update based on the associated ballot numbers.

4. The method of claim 2, wherein each of the first update and the second update further comprises an associated consensus decree, and further comprising determining a quorum set for a consensus decision on the associated consensus decrees.

5. The method of claim 1, wherein the first update and the second update may be implemented in any order.

6. The method of claim 1, further comprising one of the plurality of computing devices sending a message to the other of the plurality of computing devices, the message comprising a ballot number greater than a current active ballot number, and receiving information about the state of the other computing devices in return.

7. The method of claim 6, further comprising each of the other computing devices disabling a current leader of the computing devices.

8. The method of claim 7, wherein disabling the current leader comprises refusing messages having a lower ballot number than the ballot number received from the one of the plurality of computing devices.

9. The method of claim 8, further comprising the one of the plurality of computing devices receiving a quorum of acknowledgements on the message, and enabling a configuration based on the message.

10. A method of fault tolerant state machine replication by a plurality of computing devices, comprising:

generating a sequence of consensus decisions, each consensus decision comprising a configuration context that allows for applying the consensus decisions in any order; and

applying the consensus decisions to at least a portion of the plurality of computing devices.

11. The method of claim 10, further comprising determining a quorum set for one of the consensus decisions.

12. The method of claim 11, wherein applying the consensus decisions comprises applying the consensus decisions based on the quorum set.

13. The method of claim 10, wherein each of the consensus decisions may be generated without a quorum of acknowledgements on any of the other consensus decisions.

14. A computing system, comprising:

a data operations state machine that maintains replicated data via a sequence of consensus decisions; and

a quorum configuration state machine that determines a quorum sequence comprising a unique sequence of quorum configurations.

15. The system of claim 14, wherein the data operations state machine executes an operations sequence comprising the sequence of consensus decisions, the sequence being without reconfigurations.

16. The system of claim 14, wherein the quorum configuration state machine determines a ballot number and a leader computing device for each quorum configuration.

17. The system of claim 14, wherein the data operations state machine comprises a command that indicates that a state has transferred to a quorum configuration corresponding to a ballot number.

18. The system of claim 14, further comprising a leader computing device and additional computing devices, wherein the leader computing device performs a reconfiguration and stores a command at a ballot number on the additional computing devices.

19. The system of claim 18, wherein the command indicates that a state has transferred to a quorum configuration corresponding to the ballot number.

20. The system of claim 14, wherein the data operations state machine generates a plurality of decisions that are orthogonal to a plurality of decisions generated by the quorum configuration state machine, such that the data operations state machine continues operating when a reconfiguration decision is made by the quorum configuration state machine.