In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phase

Question

In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a prepare phase, and an accept phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

In addition, I found a number of sources which indicate there are three phases in Paxos: an accept phase, propose phase and a learning phase, in which a distinguished learner informs all other participants of the chosen value. For example: http://pdos.csail.mit.edu/6.824-2007/labs/lab-8.html

Which is true?

If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?

Explanation / Answer

Q1: Lamport describes a round of Paxos as two phases: a prepare phase, and an accept phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

I don't think Lamport uses the term "round" to organize the two phases, at least it is not the case in the "Paxos Made Simple" paper. Actually, the word "round" only occurs once in that paper and it is used to refer to the communication round.

The term "round" is used in James Aspnes' lecture notes to refer to

the collection of all messages labeled with some particular proposal n.

It is important to distinguish between the definition of "round" here and the "communication round". In this sense, a round is dedicated to a single proposal (and belongs to a single proposer), because different proposals have globally unique timestamps.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.