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

$\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
    Jun 27, 2020 at 22:32

3 Answers 3

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.

$\endgroup$
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.

$\endgroup$
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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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