Paxos algorithm: Dependency of Accept and Prepare phases

Question

Paxos algorithm generally represented in 2 phases:

1. Prepare phase
2. Propose (or Accept) phase

Each phases request are send to Acceptors which making decisions. All requests are equipped with unique ids and Acceptors store max received id across all requests.

I have a little misunderstanding, whether there is dependency on Prepare phase in Accept phase.

Both phases are gathering Quorums, so some nodes in Accept phase may yet not receive a Prepare phase request. But due to algorithm in Accept phase Acceptor compare received id with max local id, and hence can decide updating local id and responding to Proposers.

Is that correct that Acceptor can answer on Accept phase request without corresponding Prepare phase request, or not?

I’ve tried to deduce it from “Paxos made simple” and “The Part-Time Parliament” articles and couldn’t find an answer.

Answer 1

If we look at Paxos Made Simple page 5 paragraph 1:

A proposer issues a proposal by sending, to some set of acceptors, a request that the proposal be accepted. (This need not be the same set of acceptors that responded to the initial requests.)

That directly answers your question:

Is that correct that Acceptor can answer on Accept phase request without corresponding Prepare phase request, or not?

If the proposer doesn't have to send an accept message to the same agents that it sends the prepare message, then agents replying to the second phase do not have to have participated in the first phase.

The smallest practical cluster size is three nodes. Let's say that node A is leading. It sends prepare(11) to the other two nodes. These are in different cloud resilience zones or cloud regions. The network to B is broken. Yet C responds with prepare_ack(11) and node A will self-acknowledge. We now have a majority from the first phase under the initial network conditions.

Now imagine that the network link to B comes back up, and the link to C goes down.

Node A had seen the response from C and its self-response. It checks that no other prior value has been accepted based on the response messages. It is free to pick its own value to fix so it picks v1 and will send accept(11, v1) to all nodes.

Under the new network conditions Node C never gets the message. Node B does respond. It responds with accept_ack(11). Node A will respond to itself accept_ack(11). The value is now chosen.

We can think through how the above scenario can go wrong and lead to a different outcome. The critical point here is that the multiple rounds, through multiple attempts to fix a value, must use a majority. Majorities overlap. It does not matter if any given node is not part of any given majority. The Paxos algorithm will ensure that node A collaborates with any prior leader to select a consistent value. You may enjoy an article that I wrote here that highlights the collaborative nature of Paxos that aids in a more intuitive understanding of how it works.

Answer 2

Paxos algorithm actually work on three phases - the first two phases act to build consensus around a value which is then communicated in third phase.
Referencing Martin Fowler's blog:

In the first phase (called prepare phase), the node proposing a value (called a proposer) contacts all the nodes in the cluster (called acceptors) and asks them if they will promise to consider its value. Once a quorum of acceptors return such a promise, the proposer moves onto the second phase. In the second phase (called the accept phase) the proposer sends out a proposed value, if a quorum of nodes accepts this value then the value is chosen. In the final phase (called the commit phase), the proposer can then commit the chosen value to all the nodes in the cluster.

Hence, to answer your question, acceptor requires a corresponding prepare phase request to promise a value during accept phase. If the id of the prepare request is later than its promised one, acceptor updates its promise generation with this later value and returns a promise response. If it has already accepted a proposal it returns this proposal. When proposer receives promises from quorum of acceptors, it looks to see if any of these values contain accepted values. If so it changes its own proposed value to that of the returned proposal with the highest id. This then becomes the proposed value to be committed.