CODEWITHSUNDEEP
consensuspaxos
narengi
narengi

Reputation: 1405

Do proposal numbers need to be unique in Paxos?

What can happen if two proposals are issued with the same ProposalId? It shouldn't create any problem if they have the same value. But what about different values? I can work out a scenario where it risks liveness at the time of failure, but would it create any problem for the protocol's safety?

Upvotes: 1

Views: 324

Answers (2)

Joshua Anderson
Joshua Anderson

Reputation: 97

The Synod algorithm technically does not require the proposal numbers to be unique among all processes. And the monotonically increasing requirement is only an optimization. We could technically choose a random proposal number, and still have a correct algorithm.

The algorithm starts off with a proposer sending a prepare(proposal number) to all acceptors. It can then only uses that proposal number in a proposal if a majority of acceptors haven't seen a proposal number as high as or higher than that yet and successfully send back a promise which can only happen once per proposal number. After this stage, if the proposer is able to continue, then that proposal number is effectively unique. So the algorithm already enforces the uniqueness of proposal numbers that are actually used in a proposal.

Upvotes: 0

Michael Deardeuff
Michael Deardeuff

Reputation: 10697

It's a nice idea because it would ease an annoying design requirement for a practical system: designing a scheme to ensure proposers have different, yet increasing round numbers.

It doesn't work, unfortunately.

Let's define PaxosPrime to be a variation of Paxos where different proposers are allowed to have the same round numbers. We show through contradiction that PaxosPrime is not a consensus algorithm.

Proof sketch: Assume PaxosPrime is a consensus algorithm. Let's consider where each acceptor has a different value, but with the same round (w.l.o.g we'll pick 3). Each will also have promised at 3. We then have a pair of proposers interact in the system.

A1    | A2    | A3
v   p | v   p | v   p  
------+-------+------
x@3 3 | y@3 3 | z@3 3
  1. P1 prepares for round 4 (i.e. Phase 1.A) and receives all three values x@3, y@3, and z@3. There is no provision in Paxos for tie-breaking, so we'll have it choose x.
  2. P2 also prepares for round 4 and receives y@3 and z@3 from A2 and A3, respectively. We'll have it choose y.
  3. P1 sends accepts for x@4 (i.e. Phase 2.A) and the acceptors all process it. At this point all the acceptors have value v@4 and promises for 4. The system has consensus on the value x.
  4. P2 sends accepts for round y@4 and the acceptors A2 and A3 successfully process it. A majority of the acceptors now have value y@4; The system has consensus on the value y.

Here is the trace from the acceptors' point of view:

A1    | A2    | A3
v   p | v   p | v   p  
------+-------+------
x@3 3 | y@3 3 | z@3 3  # Start
x@3 4 | y@3 4 | z@3 4  # Process P1's propose command
x@3 4 | x@3 4 | x@3 4  # Process P1's accept command
x@3 4 | y@3 4 | y@3 4  # Process P2's accept command

The system first had consensus on the value x then consensus on the value y. This is a contradiction on the definition of consensus; thus PaxosPrime is not a consensus algorithm.

∎

Upvotes: 1

Related Questions