What is “value of the highest-numbered proposal” in the Paxos algorithm?

Question

In Paxos made simple Lamport describes Phase 2 (a) of the algorithm as following:

If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

• Does this mean that a proposer can send an accept request as soon as he has gathered an response from a majority of the acceptors regardless of their proposal numbers? (I find the emphasized part of the quote to imply so, because all equally-numbered proposals should have the same value, right?)
• Or does the proposer need responses with the same proposal number from the majority of the acceptors? (Meaning that responses with a number m (being less that n) don't count towards the majority for responses numbered n)

Answer 1

Does this mean that a proposer can send an accept request as soon as he has gathered an response from a majority of the acceptors regardless of their proposal numbers? (I find the emphasized part of the quote to imply so, because all equally-numbered proposals should have the same value, right?)

Yes, the proposer can send an accept request as soon as she has gathered a response from a majority of acceptors. The returned proposal numbers tell the proposer which value to send in the accept request.

If the no proposal numbers are returned, the proposer is free to choose its own value. But if any proposal number is returned, the proposer must send the value associated with the highest proposal number.

Here's an example. Let's say the proposer sends out Propose(4) to five acceptors and receives back Ack(abc, 2), Ack(abc, 2), and Ack(xyz, 3) it must send Accept(xyz, 4).

Answer 2

In paxos, you have to distinguish the proposal number, promised number, accepted number.

The response contains a proposal number and a accepted number. In the response, the proposal number is the same as the proposal, and the accepted number is the one that the Acceptor accepted before.

A proposer can send an accept request as soon as he has gathered responses from a majority of the acceptors.

Every proposal has a unique proposal number, and the proposer send the proposal without a value contained inside. The acceptor will response the same the proposal number, the accepted number and the value accepted in previous rounds. Then the proposer choose the value, either as the value of the highest-numbered proposal among the responses, or any value if the responses reported no proposals.