Paxos for System Builders




About Us

People

Research

Publications

Funding

Download




SMesh

Paxos-SB

Steward

Prime

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

  • 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. Invited paper.
     
  • Paxos For System Builders
        Jonathan Kirsch, Yair Amir
        Technical Report CNDS-2008-2.
     

Questions or comments to:
webmaster@dsn.jhu.edu
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