CODEWITHSUNDEEP
distributed-systempaxos
nz_21
nz_21

Reputation: 7383

Can multiple values be accepted in a single run?

Consider the following flow :

Proposer prepares a message, gets a promise, sends a proposal with some value, gets it accepted. All fine.

After acceptance, another proposer comes along and prepares a message with a higer id, and the same flow continues.

Is this a valid flow of a single round of the paxos algorithm? Or is this actually multi paxos?

Upvotes: 0

Views: 206

Answers (2)

simbo1905
simbo1905

Reputation: 6862

It depends if you mean "can multiple values be fixed" in a given round of Paxos or if you mean "can any given node accept more than one value".

As per the accepted answer by @Rakis you cannot get more than one value that is fixed into a location. Yet due to message loss, you can have a node accept more than one value into a location before the location is fixed.

To understand how this can happen we can image arbitrary messages getting lost arbitrary nodes crashing. For example nodes {A, B, C, D, E} with A the leader. It issues a prepare, gets a majority response, issues an accept(Va) then crashes and never recovers. The accept message is only seen by node B due to lost messages. Node E times out and issues a prepare. Due to message loss, this is only seen by nodes C, D and E. Node E has a majority response but does not know about the value Va sent by node A and accepted by node B. It is free to choose its own value and issues accept(Ve). This time all messages get through. Node B accepts Ve along with nodes C, D and E.

In that scenario, the only value fixed by the algorithm was Ve. Yet node B accepted two different values Va and Vb.

To answer your question is this multipaxos the answer is no. See this answer for the explanation about mutltipaxos is. Note it isn't helpful to call things Paxos and Multi-Paxos. In his 2019 lectures, the inventor talks about the Single Synod Algorithm for the minimal algorithm to fix a single value. Then the actual algorithm that is practically useful is the extension to choose many values from a stable leader. See this post about that. If you are sitting exams of the topic you may need to stick with the old confusing terminology.

Upvotes: 0

Rakis
Rakis

Reputation: 7874

After acceptance if another proposer comes along and prepares a message, it will receive at least one reply containing the previously accepted value. The Paxos rules then require that the second proposer MUST propose the previously accepted value. The value it wants to propose is overridden by the first value. This ensures that only a single value can be chosen for a single instance of the Paxos algorithm.

Upvotes: 1

Related Questions