2

I am looking for a simple explanation of the Paxos algorithm that can be used for reaching consensus in a distributed environment (possibly peer to peer network).

Every explanation I have encountered so far was a tough reading of multiple pages. I am looking for a simplified explanation that still preserves the core principles.

3
  • 3
    What exactly is confusing you?
    – yannis
    Dec 5, 2013 at 14:48
  • I am a total newbie to this field... every explanation I have encountered so far was a tough reading of multiple pages. Looking for a rather simplified explanation that still preserves the core principles.
    – Kozuch
    Dec 5, 2013 at 16:41
  • That depends on what you would include under "core principles". Oleksi's answer could suffice, or not. Does it?
    – JensG
    Dec 6, 2013 at 18:35

1 Answer 1

7

I've found this explanation in the context of Cassandra lightweight transactions useful.

Prepare/promise is the core of the algorithm. Any node may propose a value; we call that node the leader. (Note that many nodes may attempt to act as leaders simultaneously! This is not a “master” role.) The leader picks a ballot and sends it to the participating replicas. If the ballot is the highest a replica has seen, it promises to not accept any proposals associated with any earlier ballot. Along with that promise, it includes the most recent proposal it has already received.

If a majority of the nodes promise to accept the leader’s proposal, it may proceed to the actual proposal, but with the wrinkle that if a majority of replicas included an earlier proposal with their promise, then that is the value the leader must propose. Conceptually, if a leader interrupts an earlier leader, it must first finish that leader’s proposal before proceeding with its own, thus giving us our desired linearizable behavior.

Paxos in Cassandra

References

http://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0

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