About Us
People
Current
Research
Publications
Funding
Download
SMesh
Spines
Spread
Secure Spread
|
Paxos for System Builders
Overview
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
achieved.
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.
Contributors
- Johns Hopkins University
- Yair Amir
- Jonathan Kirsch
Software
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.
License
Paxos-SB may be freely used and distributed under some
conditions. Please review the license
agreement for more details.
Download
Source code can be downloaded here.
Related Publications
|