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.

Kozuch
  • 361
  • 2
  • 9
  • 3
    What _exactly_ is confusing you? – yannis Dec 05 '13 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 05 '13 at 16:41
  • That depends on what you would include under "core principles". Oleksi's answer could suffice, or not. Does it? – JensG Dec 06 '13 at 18:35

1 Answers1

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

Oleksi
  • 11,874
  • 2
  • 53
  • 54