# Paxos: Instances, Rounds, Phases

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?

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.

Q2: I found a number of sources which indicate there are three phases in Paxos. Which is true?

As explained in James Aspnes' lecture notes,

Note that acceptance is a purely local phenomenon; additional messages are needed to detect which if any proposals have been accepted by a majority of acceptors. Typically this involves a fourth round, where acceptors send accepted(n, v) to all learners.

In the "Paxos Made Simple" paper, Lamport mentions the "learning" phase in Section 2.3 (see Page 6). Notice that it is a fourth phase in Aspnes' lecture note.

Q3: 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?

In the classic formalization of Paxos, there are three roles which are proposers, acceptors, and learners. Learners are required to learn the chosen value. So the "learning" algorithm in Section 2.3 is (there are other variants):

We can have the acceptors respond with their acceptances to a distinguished learner, which in turn informs the other learners when a value has been chosen.

In this approach, all acceptors send every proposal they have accepted to the distinguished learner. The distinguished learner (locally) regards a value to be chosen only when it is accepted by a majority of acceptors. Then, the chosen value is propagated to other learners.