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 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 is reliable broadcast that satisifies FIFO Order. If a process broadcasts message m1 before message m2, then no correct process delivers m2 before it delivers m1. For example, if message m1 is a deposit of $100 into your banking account and message m2 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).
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 m1 "happens before" or "causally precedes" the broadcast of message m2, then no correct process delivers m2 before it delivers m1.
For example, imagine three processes a, b and c. Process a broadcasts m1a, "Banks to charge $5 ATM fee." Process b delivers m1a then broadcasts message m1b, "That's outrageous!" Without Causal Order, process c could deliver message m1b before m1a,
m1b : "That's outrageous!"
m1a : "Banks to charge $5 ATM fee."
which doesn't make sense (what is outrageous?). Causal Order requires delivery of m1a before m1b.
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 DB1 and DB2. Process a broadcasts message m1a, "deposit $100." Process b broadcasts message m1b, "charge 10% fee." Since there is no causal relationship between the messages, this situation may arise,
DB1 : $0 + $100 - ($100 * 10%) = $90
DB2 : $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.
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).