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)
.