Causal Atomic Broadcast

Spent the other day reading up on ZooKeeper a little.  ZooKeeper is a distributed, open-source coordination service for distributed applications.  Out of the box ZooKeeper can be used for name service, configuration and group membership.  Building on ZooKeeper's primitives, you can create barriers, locks, queues, etc.

Sounds interesting enough, but what got me really interested was ZooKeeper's atomic broadcast, the guts of ZooKeeper.  Atomic broadcast is very closely related to consensus (apparently equivalent in certain asynchronous systems).  Both are fundamental problems in distributed systems.

So what exactly is atomic broadcast?  To answer this, lets work our way from Reliable Broadcast.

Reliable Broadcast

Reliable Broadcast is the weakest type of fault-tolerant broadcast.  Informally, if a correct process broadcasts a message then all correct processes eventually receive that message.  Reliable Broadcast doesn't impose any message delivery ordering.

FIFO Broadcast

FIFO Broadcast is reliable broadcast that satisifies FIFO Order.  If a process broadcasts message m₁ before message m₂, then no correct process delivers m₂ before it delivers m₁.  For example, if message m₁ is a deposit of $100 into your banking account and message m₂ is a subsequent withdrawal of $75, you most definitely want FIFO Broadcast, otherwise your bank will charge you an overdraft fee (on top of their ridiculous $5 ATM fee).

Causal Broadcast

Sometimes FIFO Order is not enough because FIFO ordering too limited in context (a single process).  You need Causal Order to guarantee that if the broadcast of message m₁ "happens before" or "causally precedes" the broadcast of message m₂, then no correct process delivers m₂ before it delivers m₁.

For example, imagine three processes a, b and c.  Process a broadcasts m_1a, "Banks to charge $5 ATM fee."  Process b delivers m_1a then broadcasts message m_1b, "That's outrageous!"  Without Causal Order, process c could deliver message m_1b before m_1a,

m_1b : "That's outrageous!"
m_1a : "Banks to charge $5 ATM fee."

which doesn't make sense (what is outrageous?).  Causal Order requires delivery of m_1a before m_1b.

Atomic Broadcast

Causal Order imposes a partial ordering in the system, so messages without causal relationships are logically concurrent and do not have any delivery order guarantees.  This can be problematic in some cases.  For example, imagine two replicated databases DB₁ and DB₂.  Process a broadcasts message m_1a, "deposit $100."  Process b broadcasts message m_1b, "charge 10% fee."  Since there is no causal relationship between the messages, this situation may arise,

DB₁ : $0 + $100 - ($100 * 10%) = $90
DB₂ : $0 - ($0 * 10%) + $100 = $100

which is obviously not desirably.

Atomic Broadcast imposes a Total Order on the system so that all messages are delivered in the same order, whatever that order maybe.  So in this example, it's either $90 or $100 but never $90 in one database and $100 in the other.

We can further classify Atomic Broadcast by the actual ordering it imposes.  FIFO Atomic Broadcast is then Reliable Broadcast that is FIFO Order and Total Order.  Causal Atomic Broadcast is then Reliable Broadcast that is Causal Order and Total Order.  Causal Atomic Broadcast is the strongest guarantee we've examined.

Summary

This diagram nicely summarizes Reliable Broadcast and the orderings above (taken from "A Modular Approach to Fault-Tolerant Broadcasts and Related Problems," which the above is basically a summary of).

So there you have, atomic broadcast.