Summary of Bipartisan Paxos — (Part 3/6).
This is part 3 of my summary of BPaxos. If you haven’t read part 2, you can find it here.
In this post, I will summarize what they call Unsafe BPaxos. It is an unsafe protocol in this family, but the authors propose it in the paper for educational purposes(pedagogical). The theme of this pedagogical protocol is to choose commands in a one round trip. As we know from the first protocol simple BPaxos, the commit latency is done in two rounds: one round trip to the dependency service and one round trip to the consensus service.
Unsafe BPaxos has three components.
1- Set of unsafe BPaxos nodes.
2- Dependency Service nodes.
3- Consensus Service nodes.
Unsafe BPaxos consensus service uses Fast Paxos protocol with one instance of Fast Paxos for every instance I. It also has 2f+1 fast Paxos acceptors, and f+1 Unsafe BPaxos nodes play the role of fast Paxos leaders. The classic quorums size is f + 1 and fast quorums size is f + ⌊ (f +1) /2 ⌋ + 1. In every instance I, round 0 considers being the fast round and the other rounds are classic rounds.
The Fast Paxos acceptor initialized in round 0 is as if it received a phase 2a message with distinguished value. Thus, a Fast Paxos acceptor can vote for the first proposal that it receives for instance I. 2f + 1 dependency service nodes(di) and the 2f + 1 Fast Paxos acceptors(ai) are on the same physical machine(see Figure 4).
The Unsafe BPaxos protocol starts when node bi receives a command x from a client. Upon receiving it from the client, an unsafe BPaxos node selects a globally unique instance I and sends the tuple (I,x) to the dependency service dj. Upon receiving (I,x), dj node computes its reply (I,x,deps(I)j ) and proposes the value (x,deps(I)j ), for instance I to aj (the co-located Fast Paxos acceptor). Then aj votes for the first proposal that it receives, for instance I, so aj votes for the value (x,deps(I)j ) in the instance I and relays its phase 2b votes back to bi. If bi receives a fast quorum of phase 2b votes for the same value v = (x,deps(I)j1 ) = · · · = (x,deps(I)jm ) in instance I (where m = f + ⌊ (f +1)/ 2 ⌋ + 1), then bi learns that v is chosen. bi updates its partial BPaxos graph and informs the other Unsafe BPaxos nodes as illustrated in Figure 4.
If bi does not receive a fast quorum of phase 2b votes for some value v in round 0, then it is unsure whether or not a value was chosen and begins recovery for instance I. Another Unsafe BPaxos node bj may also begin recovery for instance I if it detects that instance I has been unchosen for some time.
Unsafe BPaxos node bi recovers instance I by attempting to get a value chosen in instance I in a higher Fast Paxos round. That is, bi chooses a larger round number and executes the full two phases of Fast Paxos. If bi executes line 5 or line 11 of Algorithm 1, bi can propose the value (noop,∅), or it can contact the dependency service to see if a command x has already been proposed in instance I and then propose (x,deps(I)) where deps(I) is computed by the dependency service.
To see why Unsafe BPaxos is unsafe, consider an Unsafe BPaxos deployment with f = 2. Assume Unsafe BPaxos node bi is recovering instance Ix. bi sends phase 1a messages in round 1 to the Fast Paxos acceptors and receives the following phase 1b responses: a3 and a4 voted for (x,{Iy }) in round 0, and a5 voted for (x,{Iz }) in round 0. bi then executes Algorithm 1. The value v = (x,{Iy }) satisfies O4(v) because the fast quorum {a1,a2,a3,a4} may have unanimously voted for v in round 0. Thus, bi executes line 9 of Algorithm 1 and proposes the value (x,{Iy }). This is incorrect! It’s possible that a1 and a2 did not vote for (x,{Iy }) in round 0. For example, they could have voted for (x,{Iz }). In this case, {Iy }, the dependencies proposed by bi, were not computed by the dependency service, since {Iy } is only the union of a minority of dependency service node replies. This violates Invariant 4 and consequently Invariant 2.
End of Part 3
NEXT → Summary of Bipartisan Paxos (Part 4/6)
