Lamport’s Generalized Paxos. Generalized Paxos is an extension of Fast Paxos to solve Generalized Consensus. The algorithm has the advantage that, by the problem definition, a collision is not characterized if two acceptors accept different but compatible c-structs. In such a case, both acceptors can later extend their accepted c-structs so that they converge to the same one (since compatible c-structs have a common upper bound). C-struct sets like command histories with commutable commands, explained better in Sec- tion 3.5, might have very few incompatible c-structs, which reduces the chances of a collision to happen and favors the use of fast rounds. ⊥ Generalized Paxos relies on the Fast Quorum Requirement (Assumption 3, on page 31). It assumes that acceptors have initially accepted at round 0, lower than any other round. Since Multicoordinated Xxxxx extends Generalized Paxos, we just overview its actions here, and explain them in detail when discussing Multicoordi- xxxxx Xxxxx. Generalized Xxxxx has the following actions. 〈 〉 ∈ Propose(p, C) Executed by proposer p to propose command C Cmd. In the action, p sends a “propose”, C message to all coordinators and acceptors. (The same as in Classic Paxos.) 〈 〉 Phase1a(c, i) Executed by any coordinator c of round i to start round i . In the action, c sends a message “1a”, c, i to each acceptor a asking a to take part in round i . (The same as in Classic Paxos, except that values are now c-structs.) 〈 〉 〈 〉 Phase1b(a, i) Executed by acceptor a to join round i upon reception of message “1a”, i , if i is greater than any other round a has ever heard of. In this case, a sends a message “1b”, a, i , vrnd, vval to the coordinator of round i , where vrnd is the highest-numbered round in which a has accepted a c-struct and vval is the c-struct it accepted in vrnd. As before, this action also prevents a from executing the same action for a round smaller than or equal to i , and from accepting a c-struct for a round smaller than i . (The same as in Classic Paxos.) Phase2Start(c, i) In this action, coordinator c of round i , after receiving a “1b” mes- sage for round i coming from each acceptor in an i -quorum Q , picks a c-struct and sends it to acceptors to be extended during the round. Picking a c-struct in Generalized Consensus is like picking a value in Fast-Paxos or in our multi- coordinated consensus algorithm: if the c-struct was possibly chosen in some round j < i , the c-struct must be picked. As before, a c-struct is said to be chosen i...
Lamport’s Generalized Paxos. Generalized Paxos is an extension of Fast Paxos to solve Generalized Consensus. The algorithm has the advantage that, by the problem definition, a collision is not characterized if two acceptors accept different but compatible c-structs. In such a case, both acceptors can later extend their accepted c-structs so that they converge to the same one (since compatible c-structs have a common upper bound). C-struct sets like command histories with commutable commands, explained better in Sec- tion 3.5, might have very few incompatible c-structs, which reduces the chances of a collision to happen and favors the use of fast rounds. ⊥ Generalized Paxos relies on the Fast Quorum Requirement (Assumption 3, on page 31). It assumes that acceptors have initially accepted at round 0, lower than any other round. Since Multicoordinated Xxxxx extends Generalized Paxos, we just overview its actions here, and explain them in detail when discussing Multicoordi- xxxxx Xxxxx. Generalized Xxxxx has the following actions.
