2
$\begingroup$

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was wondering, what is so special about a majority of nodes having a value? Why is that the key fact for consensus to work on Paxos?

It says on the paper that "any two majorities have at least one acceptor in common, this works if an acceptor can accept at most one value" (page 2). Its true that if we have two majorities then at least one node between the two must be the same one, but I was not entirely sure if I fully appreciated why that was special for consensus. How does this guarantee that a single value gets accepted? Or how does it aid in that goal?

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

Improve this question
$\endgroup$
1
  • $\begingroup$ Did you find an answer to your question. I'm reading the same paper and was wondering. The author talks about majority of agents, which doesn't necessarily mean majority of equal values. For example if we have 5 agents holding the values 1 - 5, then there is no majority of agents that will yield a majority of values. $\endgroup$
    – Rahav
    Commented Jun 27, 2020 at 22:32

3 Answers 3

Reset to default
2
$\begingroup$

Let's assume there were more than 1 Majority. Then at least 1 acceptor would contribute to all majorities. This mandates, however, that this acceptor accepts at least 2 different values, a behaviour ruled out by assumption.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In the case of two majorities, why not just choose whichever value is lexographically larger? E.g., take hash(value_a) and compare to hash(value_b), and use whichever is lower to satisfy the tie. $\endgroup$
    – Eratosthenes
    Commented Dec 9, 2023 at 17:39
1
$\begingroup$

The majority requirement ensures that the electorate cannot "go in two directions" simultaneously. E.g. if you had an electorate of 6 priests, and only 3 were required to make a decision, then on one day, 3 priests might be present in the chamber, and pass value 1 for decree D, and on the next day, another three, having no knowledge of the prior day, pass a different value 2 for the same decree D, leading to inconsistency.

Because with any majority, on the second day, one of the priests was present in the prior decision (and recorded it in his ledger), he can respond to any new proposal with an accept, but include his previously accepted value, which will compel (by the protocol) the proposer to choose it, and not some arbitrary value.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In the example you cited, as long as all of the priests know that the size of the electorate is 6, then you can just create a rule saying that no decisions can be made unless a majority of N/2 + 1 (in this case, 4) priests are present. Then you won't have any inconsistency. Why not do that instead? $\endgroup$
    – Eratosthenes
    Commented Dec 9, 2023 at 17:40
0
$\begingroup$

Consensus of a certain value by Praxos is defined to be the value accepted by a majority of the acceptors.

One can view the convenience of using a majority (which has the nice intersection property you mentione din the question) as a motivating factor for defining the consensus as such.

Another reason is that it simply is the go-to option for electing a common value (once we see that using only one acceptor is out of the question).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.