Summary of Bipartisan Paxos — (Part 5/6).

This is part 5 of my summary of BPaxos. If you haven’t read part 4, you can find it here.

In this part, I will summarize the Deadlock BPaxos, which is a modified version of the unanimous protocol. It can choose command in one round and requires only a fast Q size f + ⌊ (f +1)/ 2 ⌋ + 1. Deadlock BPaxos has a liveness issue. For this reason, this protocol is a pedagogical protocol.

It maintains a weaker invariant. Imagine a Deadlock BPaxos node bi sends command x to the dependency service in the instance I, and the dependency service responds with(I,x,deps(I)). Let I′∈ deps(I) be one of I’s dependencies. Assume that that bi knows that I′ has been chosen with value(y,deps(I′)). Further, assume that I ∈ deps(I′). In this case, there is no need for bi to include I ′ in the dependencies of I!

Invariant 2 asserts that if two instances I and I′ are chosen with conflicting commands x and y, then either I ∈ deps(I′) or I′ ∈ deps(I). Thus, if I′ has already been chosen with a dependency on I, then there is no need to propose I with a dependency on I′. Similarly, if I′ has been chosen with noop, then there is no need to propose I with a dependency on I′ because x and noop do not conflict.

Let (I,x,deps(I)) be a response from the dependency service. Let P ⊆ deps(I) be a set of instances I′ such that I′ has been chosen with noop or I′ has been chosen with I ∈ deps(I′). We call deps(I) − P the pruned dependencies of I with respect to P.

Deadlock BPaxos maintains Invariant 5. Invariant 3 and Invariant 5 imply Invariant 2.

Invariant 5. For every instance I, a value v is chosen in the instance I only if v = (noop,∅) or if (I,x,deps(I)) is a response from the dependency service and v = (I,x,deps(I) − P) where deps(I) − P are the pruned dependencies of I with respect to some set P.

Every Fast Paxos acceptor maintains a partial BPaxos graph in exactly the same way as the set of Deadlock BPaxos nodes.

When an acceptor learns that an instance I has been chosen with value (x,deps(I)), it adds I to its partial BPaxos graph labeled with x and with edges to every instance in deps(I). Thus, when an acceptor receives a phase 2a message, it updates its partial BPaxos graph with the values chosen in P. When a Deadlock BPaxos node bi executes line 8 of Algorithm 2, for instance, I, it performs a much more sophisticated procedure to determine if some value v ∈ V may have been chosen in round 0. This procedure is shown in Algorithm 3.

Line 1 determines if value v has been chosen in round 0. Thus, in line 2, bi is free to propose any value that maintains invariant 5. Otherwise, there are dependencies. But simultaneously to maintain Invariant 2, bi must not propose v unless deps(I) was computed by the dependency service. Unanimous BPaxos resolves this tension by increasing fast quorum sizes. Deadlock BPaxos resolves the tension by performing a more sophisticated recovery procedure.

In lines 4 and 5, bi sends (I,x) to the dependency service nodes co-located with the acceptors in Q and receives the corresponding dependency service reply (I,x,deps(I)Q ). 2 deps(I)Q is the union of the dependencies computed by these co-located dependency service nodes.

Next, bi enters a for loop in an attempt to prune deps(I)Q until it is equal to deps(I).

Deadlock BPaxos maintains Invariant 1 by implementing Fast Paxos with the phase 2a tweak outlined in Algorithm 2 and expanded in Algorithm 3. As described above, when a node bi executes Algorithm 3, it makes sure to propose a value v if v was maybe chosen in round 0. bi proposes a different value in phase 2a only if it concludes that no value was chosen in round 0. Thus, Algorithm 3 faithfully implements Algorithm 2, and Deadlock BPaxos successfully maintains Invariant 1. As explained above, Deadlock BPaxos maintains Invariant 2 by maintaining Invariant 5.

End of Part 5

NEXT → Summary of Bipartisan Paxos (Part 6/6)