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