How to make consensus in a democratic way?

This is weird... I was writing this post on two computers and committed on one computer. But later it had been overwritten by the draft on the other computer (auto-save). It is like Blogspot's database is not Durable (tm).


Paxos Made Simple

Paxos is an algorithm (or protocol) to draw an agreement in distributed system, where nodes communicate with each other asynchronously. This agreement could be either value, state, leader, decision, or even resource (e.g., lock). Paxos is for something like this. People in a party have their own preference for dinner but they are open to other cuisines. They make consensus on a single cuisine with more than a majority of members (to make sure the members are not torn down). How can we make it possible in distributed systems? It would not be easy because the entire process should be done in a completely decentralized way as failures (either nodes or communication channels) are pervasive in such environments.

When I was a undergrad (like seven years ago), I tried to read the Lamport's original paper and gave up. Fortunately, this paper is written in plain English (not in Greek nor Mathematish) and easy to understand. Section 2 gives ideas how Paxos protocol works and its informal proof. Section 3 gives an example how to implement state machine replication based on Paxos.


Paxos Made Practical

Although the above paper gives a conceptually clear idea of how Paxos works, its implementation is not straightforward. Programmers should consider all the corner cases that can happen (e.g., what if some machines go down or new machines come in?). In this paper, Mazieres tries to fill the gap between the beautiful theorem world and the ugly real world, with many function prototypes and data structures.

This paper picks up the "state machine replication" as an example, too. I am curious that it is really a killer application of Paxos in distributed systems.


The Chubby lock service for loosely-coupled distributed systems

Chubby is a lock service, or more precisely, a reliable file storage with advisory locks. Even though Paxos is something like a swiss-army knife that can be used for virtually any synchronization needs, most programmers are not familiar with its concept (consequently, not willing to use it). Chubby brings the power of Paxos into the programmer-friendly lock service (Paxos is internally used for leader election within a Chubby cell). Chubby has a similar interface to the UNIX file system and its advisory lock scheme (voluntary read/write locks).