Paxos (computer science)

The Paxos algorithm, originally proposed by Leslie Lamport in a paper submitted in 1990 but not published until 1998, is a fault tolerant algorithm for reaching consensus in a distributed system. Within the algorithm, consensus is defined as a decision on an input value for a set of replicated state machines.

The Protocol

Paxos is an algorithm which guarantees uniform consensus. Consensus (computer science) is necessary when a set of nodes has to decide on a common value.

Uniform consensus satisfies the following properties:

1. Uniform agreement, which means that no two nodes decide differently, regardless of whether they fail after the decision was taken;
2. Validity describes the property that the value which is decided can only be a value that has been proposed by some node;
3. Integrity, meaning no node may decide twice and finally
4. Termination, every node eventually decides some value

Paxos assumes an eventual leader election to guarantee termination, which can be built by using inaccurate failure detectors. The protocol defines different roles for the nodes. There are proposers, which propose a value, and acceptors, which either accept a proposal or reject it in a way that guarantees uniform agreement. Each node may act as both proposer and acceptor. The above mentioned properties of uniform agreement can be guaranteed by Paxos whenever a majority of acceptors is alive. That means, it tolerates the failure of F acceptors out of initially 2F + 1 acceptors.

Paxos basically consists of two phases called the read and write phase. In the read phase a node makes a proposal and tries to get a promise that his value will be accepted by a majority or it gets a value that it must adopt for the write phase. In the write phase a node tries to impose the value resulting from the read phase on a majority of nodes. Either the read or write phase may fail. Proposals are ordered by proposal numbers. By using an eventual leader to coordinate different proposals, the algorithm will eventually terminate.

Usage

Google uses the Paxos algorithm in their Chubby distributed lock service in order to keep replicas consistent in case of failure. Chubby is used by Bigtable which is now in production in Google Analytics and other products.

See also

• Chandra-Toueg consensus algorithm
• State machine
• Virtual synchrony

External links

• Yale University's Wiki article
• Leslie Lamport's history of the paper
• Google Whitepaper: Chubby Distributed Lock Service
• Google Whitepaper: Bigtable A Distributed Storage System for Structured Data