advertise
« Classifying XTP systems and how cloud changes which type startups will use | Main | Cloud Programming Directly Feeds Cost Allocation Back into Software Design »
Tuesday
Mar102009

Paper: Consensus Protocols: Paxos  

Update: Barbara Liskov’s Turing Award, and Byzantine Fault Tolerance.

Henry Robinson has created an excellent series of articles on consensus protocols. We already covered his 2 Phase Commit article and he also has a 3 Phase Commit article showing how to handle 2PC under single node failures.

But that is not enough! 3PC works well under node failures, but fails for network failures. So another consensus mechanism is needed that handles both network and node failures. And that's Paxos.

Paxos correctly handles both types of failures, but it does this by becoming inaccessible if too many components fail. This is the "liveness" property of protocols. Paxos waits until the faults are fixed. Read queries can be handled, but updates will be blocked until the protocol thinks it can make forward progress.

The liveness of Paxos is primarily dependent on network stability. In a distributed heterogeneous environment you are at risk of losing the ability to make updates. Users hate that.

So when companies like Amazon do the seemingly insane thing of creating eventually consistent databases, it should be a little easier to understand now. Partitioning is required for scalability. Partitioning brings up these nasty consensus issues. Not being able to write under partition failures is unacceptable. Therefor create a system that can always write and work on consistency when all the downed partitions/networks are repaired. 

Related Articles

  • Google's Paxos Made Live – An Engineering Perspective
  • ZooKeeper - A Reliable, Scalable Distributed Coordination System
  • Impossibility of Distributed Consensus with One Faulty Process by Lynch et al
  • Consensus, impossibility results and Paxos by Ken Birman
  • Paxos for System Builders by Jonathan Kirsch and Yair Amir
  • References (1)

    References allow you to track sources for this article, as well as articles that were written in response to this article.

    Reader Comments

    There are no comments for this journal entry. To create a new comment, use the form below.

    PostPost a New Comment

    Enter your information below to add a new comment.
    Author Email (optional):
    Author URL (optional):
    Post:
     
    Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>