BANGALORE, INDIA: Paxos is a protocol for achieving consensus in a distributed system. Consensus is an important problem in distributed systems. By consensus, we mean agreeing on a single outcome and Paxos is an algorithm that helps in reaching an agreement for a single value at any point in time.

The world today is abound with several varieties of distributed systems, the Facebook servers, Twitter systems and the new breed of cloud computing systems like Windows Azure, Google AppEngine and Amazon Elastic Cloud are just a few examples wherein large scale distributed systems and architecture are deployed. Central to these systems are several class of algorithms which when implemented produce a single system consisting of a massive collection of computing nodes which is not only scalable, but self reliant, fault tolerant and also highly available.

In a distributed system, an individual functional entity- for example a file is distributed across a set of nodes. Distribution increases availability, fault-tolerance and also helps in balancing loads. But mere distribution is not enough to build a completely reliable system. To understand the problem of consensus and why it is required, let us think of distributing a single variable across a set of nodes. Several distinctive clients, each a different process, are interested in updating this single variable.

Clearly, since the request for updates is from several places and there is no direct control on ordering of the updates, the single variable in question loses the ability to maintain consistency, resulting in unpredictable results. Consensus algorithms help in alleviating problems of such kind by automatically ordering the set of updates even under worst conditions of network failure or when processes die unexpectedly so that updates occurring to a single variable distributed across the set of nodes all appear same.

Paxos was originally proposed by Leslie Lamport. He is one of the forerunners in the areas of distributed system and to his credit lies several different algorithms distributed system related to Time and Clocks, Byzantine Fault tolerance, consistency, and snapshots among others. He is also particularly noted for his contribution to LATex. Paxos was invented while he was on in his vacation in the beautiful Greek inland, Paxos and the original paper actually is a description of a parliament session organized by a lost civilization.

The characters in the papers are named after several computer scientists and depicted in a humorous way, unlike other serious computer science papers. It is however filled with complex maths and only after several years people started showing interest in this seminal work.