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.
-
3What exactly is confusing you?yannis– yannis2013年12月05日 14:48:52 +00:00Commented 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– Kozuch2013年12月05日 16:41:57 +00:00Commented 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– JensG2013年12月06日 18:35:40 +00:00Commented Dec 6, 2013 at 18:35
1 Answer 1
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