Question: How does epaxos ensure that a committed value can be recovered correctly?

[drmingdrmer]

Epaxos does not store the ballot at which an instance is accepted, which is different from classic paxos. How does epaxos guarantee that an accepted value will be chosen?

Epaxos mentioned that it will choose an accepted value, in Figure 3: The EPaxos simplified recovery procedure:

else if R contains an (γ,seqγ,depsγ,accepted) then run Paxos-Accept phase for (γ,seqγ,depsγ) at L.i

And it said that only committing a safe value is guaranteed via classic paxos:

Proposition 2. Replicas commit only safe tuples:

Proof sketch. A tuple (γ,seqγ,depsγ) can only be committed at a certain instance Q.i (1) after the Paxos- Accept phase, or (2) directly after Phase 1. Case 1: A tuple is committed after the Paxos-Accept phase if more than half of the replicas have logged the tuple as accepted (line 20 in Figure 2). The tuple is safe via the classic Paxos algorithm guarantees.

Classic paxos need to record the ballot at which a value is accepted(vrnd in the classic paxos paper), and it choose the value with the greatest ballot thus only the committed value will be chosen to commit at a higher ballot.

Epaxos impl has no such a field, only the last seen ballot. How does it guarantee the committed value will be chosen in this scenario?

With a setup with: n = 7, f = 3;

• And instance a, a recovery process with ballot=1 wrote an accepted a with a→b₂(a depends on b and seq of b is 2) at ballot=1 on replica-1(R1). Then quit.

• Another recovery process with ballot=2 successfully committed a with a→b₃(a depends on b and seq of b is 3) at ballot=2, on replicas(R2, R3, R4, R5).

• A third recovery process with ballot=3 sends Prepare to R1 then quit. Now on R1, the ballot for a is 3.

• A forth recovery process prepared on R1, R2, R3, R4. It saw two accepted value of a:

  • a→b₂, at ballot=3
  • a→b₃, at ballot=2

time | 
     | La  R1  R2  R3  R4  R5  Lb  |
     | a                       b₀  |
     |             b₁  b₂  b₃      |
     |     a   a   a   a   a       |
     |             ↓   ↓   ↓       |
     |             b₁  b₂  b₃      |
     |                             |
     |     --------------          |
     |     Recovery blt=1          |
     |     choose a→b₂             |
     |     a                       |
     |     ↓                       |
     |     b₂                      | Prepared on R1..R4;
     |     A                       | Accepted at ballot=1 by R1
     |                             |
     |         --------------      |
     |         Recovery blt=2      |
     |         choose a→b₃         |
     |         a                   |
     |         ↓                   |
     |         b₃                  | Prepared on R2..R5;
     |         A   A   A   A       | Accepted at ballot=2 by R2..R5
     |                             |
     |     --------------          |
     |     Recovery blt=3          |
     |     a                       |
     |     ↓                       |
     |     b₂                      | Prepared on R1 with ballot=3;
     |     A                       | 
     |                             |
     |     --------------          |
     |     Recovery blt=4          |
     |                             | Prepared on R1..R4
     |                             |
     v

After these steps, recovery with ballot=4 would see two accepted value a→b₂ at ballot=3 on R1, and a→b₃ at ballot=2, on R2, R3, R4.

Now what an accepted value could be chosen by the recovery process with ballot=4?

Thank you for your great work and for the help you provided. :DDD

[vitorenesduarte]

I haven't read the example but it has been reported that a single ballot is insufficient: On the correctness of Egalitarian Paxos or this document by @mwhittaker.

[drmingdrmer]

Thanks a lot! I'm gonna have a look at this paper. And a fixup would be quite easy.