1

So, I’m studying Paxos and the Professor made this question:

Assume that acceptors do not change their vote. In other words, if they vote for value v in round i, they will not send learn messages with value different from v in larger rounds. Show that Paxos does not work any more (it can reach a livelock).

I’ve reasoned about this for the entire day, but I’m not understanding how can the livelock arises and so my colleagues.

Does anyone have a clue?

eddie
  • 45
  • 1
  • 4

1 Answers1

1

Assume there were network failures such that every acceptor accepted a different value. Without the ability to change their value in future rounds, no progress could ever be made and you have a "livelock".

Rakis
  • 7,779
  • 24
  • 25
  • I deleted my previous comment, I realized it was wrong. Anyway you can't build a situation like the one you described: pick 3 acceptors, you'll eventually have 2 acceptors which voted one for v and the other one for v', while the third never voted. A proposer will now collect at least 2 promises with one associated with a previous vote. Since one has never voted, it will vote for either v or v' and a quorum is achieved. In this situation you have to assume that the acceptor which never voted will fail forever. – eddie Jan 16 '21 at 11:53
  • You're correct for a system with 3 acceptors however this is a special case. Consider a scenario with 5 acceptors instead of 3. You could have v, v', and v'' accepted simultaneously. If the remaining 2 accepted v and v' (or v'') you then have a live-lock where a majority cannot be reached. – Rakis Jan 17 '21 at 22:57