Paxos for System Builders
Paxos is a fault-tolerant state machine replication algorithm
developed by Leslie Lamport. Although the algorithm was known in the
1980s and published in 1998, it is difficult to understand how the
algorithm works from the original specification. Moreover, the
specification omits several critical details needed to build a real
system that uses Paxos as a replication engine.
Over the last several years, we have developed a complete
specification of our interpretation of the Paxos algorithm such that
system builders can understand it and implement it. We call the
resulting specification Paxos For System Builders. We are not
the first to try to cleanly specify Paxos. What distinguishes our work
from previous approaches is its dual emphasis on (1) specifying the
protocol such that it will lead to a simple and efficient
implementation and (2) bringing to light the theoretical implications
of the various design choices one makes in filling in the details
needed to implement Paxos. Our research has shown that how one fills
in these missing algorithmic and systems-related details can have a
dramatic effect on the performance and liveness properties of the
protocol. These details include which protocol is used to elect a
leader, how servers recover missed messages, and how flow control is
We implemented Paxos For System Builders and it is available
to the research community. Our implementation is optimized
and includes batching and aggregation techniques that dramatically
improve performance and reduce overhead.
- Johns Hopkins University
- Yair Amir
- Jonathan Kirsch
The first version of Paxos-SB was released in August 2012. It is written in C and has been tested on
Linux and Mac OS X.
Paxos-SB may be freely used and distributed under some
conditions. Please review the license
agreement for more details.
Source code can be downloaded here.
- Paxos For System Builders: An Overview
Yair Amir, Jonathan Kirsch
In Proceedings of the 2008 Workshop on Large-Scale Distributed Systems and Middleware (LADIS 2008), Yorktown, NY, September 2008.
- Paxos For System Builders
Jonathan Kirsch, Yair Amir
Technical Report CNDS-2008-2.
Questions or comments to:
TEL: (410) 516-5562
FAX: (410) 516-6134
Distributed Systems and Networks Lab
Computer Science Department
Johns Hopkins University
3400 N. Charles Street
Baltimore, MD 21218-2686