paxos algorithm - how does the propose stage work?

Question

I am looking at the pseudocode for the PROPOSE stage of the paxos algorithm: https://www.cs.rutgers.edu/~pxk/417/notes/paxos.html

did I receive PROMISE responses from a majority of acceptors?
if yes
    do any responses contain accepted values (from other proposals)?
    if yes
        val = accepted_VALUE    // value from PROMISE message with the highest accepted ID
    if no
        val = VALUE     // we can use our proposed value
    send PROPOSE(ID, val) to at least a majority of acceptors

If one of the peers has previously accepted a value (accepted_VALUE), what happens to the value that the proposer is trying to propose (VALUE)?

As I understand it looking at the pseudocode, it gets discarded? That seems like a loss of information...

Answer 1

The proposer does discard its value when an acceptor responds with a value.

I think of it like this: Paxos is a cooperation protocol, much like a wait-free-lock-free algorithm. The proposer's job is not to ensure its value is chosen, but to help the process along. When a proposer sees that it was beat out by another proposer, it helps to replicate that other proposers.

In a similar vein, you can think of it as the proposer is continuing the work of a prior, potentially dead proposer.

You can see this more clearly in the simpler, non-consensus Attiya/Bar-Noy/Dolev (ABD) protocol. Even when reading in ABD the "proposer" re-writes the value to the peers to ensure the value is distributed across the system.

---

ABD: "Sharing memory robustly in message-passing systems", H. Attiya, A. Bar-Noy, and D. Dolev, 1995