Paxos algorithm generally represented in 2 phases:
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.
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.