Skip navigation

Agreement Protocol

Headline: We now have a robust declarative implementation of MultiPaxos with leader election, which is radically simpler than most existing implementations.  It’s compact, suprisingly readable (as Paxos implementations go!) and live.  It forms a key part of our Boom Analytics implementation of a high-availability Hadoop File System.

Maybe more interesting are the lessons we learned about how distributed protocols and declarative languages go together, and the design patterns that emerged.  We’re using this to ground the design of our new language, code-name Lincoln.  A paper on the topic is being presented this Wednesday at NetDB 2009, after SOSP.

Jim Gray used to compare agreement protocols like two-phase commit to the Christian marriage ceremony:

  • Officiant: “Do you take this …”
  • Bride: “I do.”
  • Groom: “I do.”
  • Officiant: “I now pronounce you…”

Leslie Lamport went for more exotic analogies with his Paxos protocol for distributed consensus in the presence of failures.  Paxos has become something of a litmus test for distributed foo (see here and here) — it’s a bit of a challenge to understand, and has to be coupled with a few other distributed systems nuggets before it becomes practical.

We’ve written about our declarative implementations of these protocols in a paper for NetDB.  Riffing a bit on Jim Gray’s analogy, the paper is entitled “I Do Declare: Consensus in a Logic Language”.  It lays out our experience writing two-phase commit in Overlog, and then writing Paxos as well.  Along the way, we found some common design patterns or “idioms” we needed, which are illustrated in the diagram below.  Basically, Overlog gives you higher-level primitives than Java or C, say, but along the way we used them to build even higher-level “idioms” that seem to make sense for these kinds of protocols:

Design patterns used in declarative 2PC and Paxos implementations

Design patterns used in declarative 2PC and Paxos implementations

Supposing you want to write a good programming language for building distributed systems (as we do), where in this graph do you take a cut and choose operators for the language?  Where in the graph do you choose to build libraries for reuse?  I like this line of questioning because it gets us away from Datalog roots and more deeply into questions of language design, including whether the world needs a domain-specific language for the hard bits in building distributed systems, or a new general-purpose language that is targeted at distributed architectures.  This is going to be a hot topic for our group over the coming months.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: