What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple) 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
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.