Simple Consensus Under Synchrony and Crash Faults

Consensus is at the heart of replicated databases, distributed coordination, and fault-tolerant computing. Algorithms such as Paxos and Raft solve more complex versions of this problem, but their details can be difficult to understand when first encountering the subject.

Fortunately, there is a much simpler place to start. In this post, we’ll look at the simplest nontrivial setting for distributed consensus and explore two algorithms that solve it.

Imagine a group of computers, each starting with its own proposed value. Their task is to agree on one value.

A correct consensus algorithm must satisfy three properties:

The challenge is that some computers may fail while the algorithm is running.

If no failures were possible, consensus would be easy: designate one computer to announce its value, and everyone else adopts it. Failures are what make the problem interesting.

This is arguably the simplest nontrivial consensus problem: failures are possible, but we have reliable timing guarantees and do not have to worry about malicious behavior.

Let’s see how two surprisingly simple algorithms solve it.

The first algorithm is based on a simple idea: Keep sharing all the proposed values you have learned.

Each process maintains a set of known values. Initially, this set contains only its own proposal. In each round, every process sends its entire set to every other process and adds any newly received values to its set. After (f+1) rounds, each process decides the smallest value in its set.

Here is the complete (really, it is this simple!) algorithm:

initalize S = {my proposed value}Repeat f+1 times: Send S to everyone Receive sets from others Add all received values to SDecide the smallest (or largest) value in S

Press enter or click to view image in full size

An Illustration of the FloodSet algorithm in action

Why does FloodSet work?

The key insight is that a value cannot remain hidden from some surviving processes indefinitely without crashes occurring.

If a process knows a value at the beginning of a round and survives the round, it sends that value to everyone.

If it crashes midway through sending, the value might reach only some processes. But those processes can forward it in the next round.

For a value to keep spreading incompletely across successive rounds, a new crash must interrupt its propagation each time.

Since at most (f) crashes can occur, (f+1) rounds are sufficient to ensure that all surviving processes have the same information.

Notice that FloodSet does not require a leader. Everyone participates equally.

The second algorithm is even simpler in terms of communication.

Instead of everyone sending information to everyone, we designate (in advance) a different coordinator in each round.

The coordinator announces its current value, and everyone who receives it adopts that value.

If the coordinator crashes, we simply move on to the next coordinator.

After (f+1) rounds, everyone decides. Here it is as pseudocode:

Initialize v = my proposed valueFor r = 1 to f+1: Process r broadcasts its current v If I receive that value: v = the received valueDecide v

We assume the processes are numbered 1 through (n), so the first (f+1) processes can serve as coordinators.

An illustration of the rotating coordinator algorithm in action

Why does rotating coordinator work?

Here is the beautiful observation: Among (f+1) coordinators, at least one must be nonfaulty.

Suppose round (r) is the first round with a nonfaulty coordinator.

That coordinator successfully broadcasts its value to everyone. By the end of the round, all surviving processes have the same value.

Could a later coordinator destroy this agreement?

No. Every later coordinator is either already among the surviving processes that adopted this common value, or has crashed and therefore cannot send anything. Any value it broadcasts must therefore be the same value.

Consequently, once a nonfaulty coordinator has broadcast, agreement is permanent.

And because there are at most (f) crashes, at least one of the first (f+1) coordinators must be nonfaulty.

There is no voting, no majority quorum, and no complicated leader election. The coordinator schedule is fixed in advance.

Both algorithms solve the same problem, but they use different strategies.

FloodSet illustrates a very general technique in distributed systems: propagate information until everyone has a consistent view. The rotating-coordinator algorithm is more communication-efficient.

Both algorithms finish after exactly (f+1) rounds, even if fewer than (f) processes actually crash. More advanced algorithms can sometimes decide earlier when failures are absent or limited.

The assumption of synchrony is doing a great deal of work here.

Imagine a coordinator sends no message during its round.

In a synchronous system, everyone knows when the round has ended. They can safely move on to the next coordinator.

In an asynchronous system, however, there is no known upper bound on message delivery time. A missing message could mean either that the coordinator crashed or that its message is simply delayed.

The famous Fischer–Lynch–Paterson (FLP) impossibility result shows that, in a fully asynchronous system, no deterministic consensus algorithm can guarantee termination in every execution if even one process may crash.

This does not mean consensus is impossible in practical asynchronous networks. Rather, it means we need additional assumptions or mechanisms, such as timing assumptions, failure detectors, or randomization, to obtain the guarantees we want.

Synchrony removes this particular obstacle by giving processes a reliable notion of when to advance to the next round.

These two algorithms illustrate two important ways to achieve consensus.

FloodSet achieves agreement by spreading information until every surviving process has learned enough to make the same decision.

Rotating coordinator achieves agreement by giving successive leaders the opportunity to impose a common value, knowing that at least one coordinator must eventually complete its broadcast, given the bound on number of faults.

Both rely on the same fundamental fact: there can be at most (f) crashes, so (f+1) rounds are enough.

Of course, real distributed systems often have to deal with more difficult conditions: uncertain network delays (requiring partial synchrony or probabilistic assumptions), temporary disconnections, process recovery, and even malicious participants. Those complications motivate more sophisticated protocols. But the basic problem and two simple solutions presented here are a good start.

Consensus does not have to be complicated. Under synchrony and crash-stop failures, it can be solved with just a few lines of pseudocode and remarkably simple correctness arguments.

Hagit Attiya and Jennifer Welch (2004). Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edition, Chapter 5.

X. Wang, J. Cao, and Y. M. Teo, “An approach to achieve message efficient early-stopping uniform consensus protocols,” in Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), Hong Kong, 2004, pp. 300–306.

AI use statement: I used ChatGPT for this post; the post including the text and figures are based on my initial idea, inputs, verification, and interactive refinement for clarity and ease of understanding.