0
$\begingroup$

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was reading page 4 of the paper where it says condition $P2^c$:

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that

  • (a) no acceptor in S has accepted any proposal numbered less than n, or

  • (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

(Where S = any set consisting of a majority of acceptors. C = the set of acceptors that have accepted some value c, the letter C stands for the majority that has Chosen a value).

I was trying to understand better the conditions for issuing a proposal, specifically (b) is the one causing troubles for me.

For me (a), makes sense because we don't want to issue a new proposal with a higher sequence number if there has been any proposal that has been chosen from the majority we are able to see (i.e. S). Since anything that has been chosen is accepted and since something chosen is part of the majority C, if we issue a new proposal, we could risk confusing the current paxos instance when its already chosen a value.

However, (b) is less clear to me why we want it to hold. Recall (b) is:

(b) = "v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S".

Why are we interested in having that condition? Which safety properties does that condition help us maintain?


Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

$\endgroup$
  • 3
    $\begingroup$ You have posted a number of questions on the same paper. Are you trying to outsource some kind of assignment? In any case, please format your posts more carefully. Shorter titles, appropriate tags and useful Markdown formatting go a long way towards making people read your questions. $\endgroup$ – Raphael Mar 31 '14 at 8:25
  • $\begingroup$ No assignment. Just studying the papers. $\endgroup$ – Pinocchio Mar 31 '14 at 16:23
  • $\begingroup$ I have put some time in thinking about to ask my questions and specially what title to put to them, if you have a specific suggestion on how to change it I would gladly change it! :) $\endgroup$ – Pinocchio Mar 31 '14 at 16:24
  • 1
    $\begingroup$ There is no homework tag. As for the other points, feel free to do what you think is best. $\endgroup$ – Raphael Mar 31 '14 at 17:34
  • 2
    $\begingroup$ A question asking for Lamport's rationale is unanswerable (except by the author), and is inappropriate for SE. There's nothing to be said beyond repeating the paper: the invariant is utilized by the algorithm to guarantee the agreement condition of the consensus problem. $\endgroup$ – VF1 May 28 '14 at 23:28
2
$\begingroup$

The paper already gives a detailed explanation to motivate that condition and explain why it is useful to prove that a protocol meets that condition. Read the development in Section 2 of the paper; it lays the chain of reasoning out very nicely.

To summarize: P2c helps us prove P2b; P2b helps us prove P1 and P2; P1 and P2 help us ensure that we meet the safety requirements outlined at the start of Section 2.1.

So, to answer your question "Which safety properties does that condition help us maintain?": that condition helps us maintain the three safety properties specified at the start of Section 2.1 of the paper (as the paper already explains).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.