Virtually synchronous Paxos
First Claim
1. A method for updating a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:
- a leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, where the first data state update comprises a first ballot number;
the leader proposing the first data state update to the plurality of computing devices;
the leader generating a second data state updates for the state machine resulting from a second requests from a second client operating on the state machine, the second data state update comprising a second ballot number;
the leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements from the plurality of computing devices for the first data state update;
the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update; and
the state machine implementing the second data state update, if a quorum of acknowledgements is received from the plurality of computing devices for the second data state update.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. A method for updating a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:
-
a leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, where the first data state update comprises a first ballot number; the leader proposing the first data state update to the plurality of computing devices; the leader generating a second data state updates for the state machine resulting from a second requests from a second client operating on the state machine, the second data state update comprising a second ballot number; the leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements from the plurality of computing devices for the first data state update; the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update; and the state machine implementing the second data state update, if a quorum of acknowledgements is received from the plurality of computing devices for the second data state update. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method for reconfiguring a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:
-
a first leader of the plurality of computing devices sending a message to the plurality of computing devices, the message comprising a state machine configuration update and a ballot number higher than a current ballot number used by a second leader for the state machine; one or more of the plurality of computing devices disabling the second leader by refusing messages comprising a ballot number lower than the first leader'"'"'s; after receiving a quorum of acknowledgements from the plurality of computing devices, the first leader; generating a plurality of data state updates for the state machine resulting from a plurality of requests from one or more clients operating on the state machine, the respective plurality of data state updates comprising different ballot numbers; and proposing the plurality of data state updates to the plurality of computing devices without regard to receiving a quorum of acknowledgements for the respective plurality of data state updates; and the state machine implementing the one or more plurality of data state updates, if the quorum of acknowledgements is received for the respective plurality of data state updates. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19)
-
-
20. A method for updating and reconfiguring a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:
-
a first leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, the first data state update comprising a first ballot number; the first leader proposing the first data state update to the plurality of computing devices; the first leader generating a second data state update for the state machine resulting from a second request from a second client operating on the state machine, the second data state update comprising a second ballot number; the first leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements for the first data state update; the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update; the state machine implementing the second data state update, if the quorum of acknowledgements is received for the second data state update; a second leader of the plurality of computing devices sending a message to the plurality of computing devices, the message comprising a state machine configuration update and a ballot number higher than a current ballot number used by the first leader for the state machine; one or more of the plurality of computing devices disabling the first leader by refusing messages comprising a ballot number lower than the second leader'"'"'s ballot number.
-
Specification