Consensus Algorithms, Underground (Part 1) — Crashes and Delays Are Indistinguishable

Consensus Is Not a Conversation

Consensus algorithms are usually described as “a mechanism by which multiple nodes agree on the same value.” That is not wrong, but what implementation and operations actually deal with is a more concrete set of failures.

Nodes stop without warning. When there is no response, one cannot determine whether the node has crashed or is merely delayed. Messages are delayed, duplicated, and reordered. Writes to disk can appear complete and still be lost. An old leader may continue to regard itself as the leader and keep processing on both sides of a network partition. In blockchains, some nodes additionally send deliberately false information.

Consensus is therefore not decision-making by discussion.

It is the act of deciding which history survives as the official record, under incomplete communication and partial failure.

This series works through Paxos, Raft, Viewstamped Replication, Zab, PBFT, Tendermint, HotStuff, Narwhal, Bullshark, Mysticeti, PoW, PoS, and the Avalanche family, viewed through the problem each one targets and the structure each one implements. Part 1 covers the substrate that no choice of algorithm can avoid.

One Word, Three Problems

The term “consensus” bundles three separate problems.

1. Choosing a leader. Determining which node is currently the write entry point.
2. Determining operation order. Making every node agree on whether SET x=1 or SET x=2 came first.
3. Committing a decision. Guaranteeing that a committed operation is not reversed after a re-election or a recovery.

The important point is that leader election alone does not constitute consensus.

Redis Sentinel, Kubernetes Leases, and ZooKeeper ephemeral nodes can all elect a leader. But if the operations that leader processed have not been persisted to a majority, they are lost at failover. Someone having been elected and that node’s work surviving are two different guarantees.

Conversely, EPaxos and DAG-BFT determine order from dependencies between operations or from certificates, without a fixed leader. A leader is a means, not an end.

Crashes and Delays Are Indistinguishable

Node A sends a request to node B and receives no response. The candidate causes are numerous.

• B’s process has stopped
• B’s OS has become unresponsive
• The path to B has been severed
• B is stalled in GC or waiting on I/O
• Communication works only in one direction between A and B
• The response was sent but lost in transit

In an asynchronous network, a crash and a delay cannot be distinguished within finite time. This is the practical meaning of FLP impossibility: in a fully asynchronous system where at least one node may crash, no deterministic consensus algorithm always terminates.

Real systems evade this constraint with the following assumptions.

• Assume a degree of synchrony by using timeouts
• Introduce randomness
• Assume a failure detector
• Halt progress temporarily while preserving safety

Raft and HotStuff take the partial synchrony model — the network eventually behaves for some period — as their practical premise. In other words, these algorithms abandon guaranteed progress by design. What they abandon is liveness; what they retain is safety.

Split Brain and Side Effects That Escape the Cluster

When the network splits in two and both sides consider themselves the legitimate cluster, the history forks.

            partition
   A ─ B   |   C ─ D ─ E
 leader    |   new leader

If writes are permitted only to a majority, the left has 2 votes and the right has 3, so only the right side can continue. This is the basis of majority quorums.

However, this protects only the inside of the cluster. An old leader can keep issuing commands to storage, job queues, external APIs, and physical equipment. A vote tally inside the cluster never reaches external resources.

Real systems therefore make the target of the side effect check a monotonically increasing generation number — term, epoch, generation, i.e. a fencing token — rather than a simple leader flag.

class FencedResource:
    def __init__(self):
        self.highest_token = 0
        self.value = None

    def write(self, token: int, value: str) -> None:
        if token < self.highest_token:
            raise RuntimeError("stale leader")
        self.highest_token = token
        self.value = value

Holding the consensus result inside the cluster is insufficient; the generation number must propagate all the way to wherever side effects are executed.

The Agreed Log and the Applied State Are Different

A typical replicated state machine separates into these layers.

client request
    ↓
 proposal
    ↓
 replicated log
    ↓
 commit
    ↓
 state-machine apply
    ↓
client response

Having been appended to the log, having been replicated to a majority, and having been applied to the state machine are three distinct events.

if replicated_to_majority(entry):
    commit_index = entry.index

while applied_index < commit_index:
    applied_index += 1
    state_machine.apply(log[applied_index])

Blurring these boundaries produces the following failures.

• Returning success to the client for a value that has not been committed
• Applying the same command twice after a restart
• Misaligning the boundary between a snapshot and the log
• Re-executing a request that was applied but whose response was lost, when the client retries

As the last item shows, consensus does not provide exactly-once semantics automatically. It provides log order and commitment, nothing more. Ensuring a request is not executed twice is handled separately, by deduplication on a client request ID.

def apply(command):
    if command.request_id in completed:
        return completed[command.request_id]

    result = execute(command)
    completed[command.request_id] = result
    return result

completed is itself part of the state machine and must be included in snapshots. Omitting it yields double application only after a restart — a failure that is difficult to reproduce.

Summary

• What consensus solves is not agreement as such, but which history survives as the official record under incomplete communication and partial failure.
• Leader election, ordering, and commitment are separate problems. Electing a leader is useless if its work has not been persisted to a majority; it is lost at failover.
• Crashes and delays are indistinguishable in an asynchronous system (FLP impossibility). Practical algorithms assume partial synchrony and trade liveness for safety.
• A majority quorum protects only the inside of the cluster. External resources must check a generation number via a fencing token.
• Appending, committing, and applying are distinct events. Exactly-once lives outside consensus, as deduplication on a request ID.

Part 2 covers the first family built on this substrate: algorithms for the crash failure model. It begins with the single tool Paxos relies on — quorum intersection — then examines how Raft decomposed it into an implementable form, and ends with the persistence ordering and snapshot rules that the papers do not state.