Total-Order Broadcast: One Order for Every Replica

Causal order is a partial order, and a partial order leaves some pairs of events unordered. A replicated state machine cannot work with that. If two clients write the same key concurrently, every replica must apply the two writes in the same sequence, or the replicas end at different values even though they saw the same set of operations. Total-order broadcast is the abstraction that supplies the missing decision: every correct process delivers every message, and all processes deliver them in the same order.

The guarantee, stated precisely

Total-order broadcast, also called atomic broadcast, has three properties:

• Validity. If a correct process broadcasts a message, it eventually delivers it.
• Agreement. If a correct process delivers a message, every correct process eventually delivers it.
• Total order. If two correct processes both deliver messages m1 and m2, they deliver them in the same relative order.

The order itself is unspecified. The protocol is free to place m2 before m1 or after, and different runs may produce different orders for the same set of concurrent messages. What is fixed is that all replicas agree on whichever order was chosen, and that the order is consistent with causality where causality exists: a message sent in response to another cannot be delivered before it, because the response was produced after the receipt.

The last point connects the abstraction to the previous articles. A total order is a linear extension of the causal partial order, so any mechanism that respects happens-before can be extended to a total order by a tie-break among concurrent messages, using the counters described in Happens-Before and the Scalar Logical Clock. The tie-break must be identical at every replica, which is what makes the problem nontrivial.

The sequencer construction

The simplest protocol uses one designated process as the sequencer. Every client sends its message to the sequencer. The sequencer assigns each message the next sequence number and forwards it to all replicas. A replica delivers messages in sequence-number order and buffers any message whose number is ahead of the next expected one.

This is total-order broadcast in the sense of the definition, provided the sequencer is correct and does not crash. The order is the order in which the sequencer received the messages, which is arbitrary among concurrent clients but identical at all replicas. Latency is two message hops: client to sequencer, sequencer to replicas. Throughput is bounded by the sequencer’s capacity, since every message passes through it.

The construction fails badly under sequencer failure. A sequencer that crashes after assigning a number but before forwarding leaves a gap in the sequence that no replica can fill. A sequencer that crashes after forwarding to some replicas but not others leaves the replicas disagreeing about what was delivered. Recovery requires a way to choose a new sequencer and to establish what the old one had done, which is exactly the problem that consensus protocols solve.

class Sequencer:
    def __init__(self, replicas):
        self.seq = 0
        self.replicas = replicas

    def broadcast(self, msg):
        self.seq += 1
        record = (self.seq, msg)
        for r in self.replicas:        # forward to every replica
            r.send(record)

class Replica:
    def __init__(self):
        self.next_expected = 1
        self.pending = {}              # out-of-order messages wait here

    def on_record(self, seq, msg):
        if seq < self.next_expected:
            return                     # duplicate, already delivered
        self.pending[seq] = msg
        while self.next_expected in self.pending:
            deliver(self.pending.pop(self.next_expected))
            self.next_expected += 1

The buffer is not an optimization. Without it, a message that arrives before its predecessor would have to be discarded or delivered out of order, and either choice breaks the guarantee. The buffer’s size is the measure of how far ahead a replica may run; a replica that receives message 100 while waiting for 3 must hold 97 messages, which is why a stalled sequencer translates into unbounded memory at the replicas.

Why consensus is required

A sequencer that can fail needs a replacement, and the replacement must not contradict the old one’s decisions. If replica A has delivered messages 1 through 50 and the old sequencer had assigned 51 to a message that only some replicas received, the new sequencer must either complete that assignment or prove it never happened. Choosing among these outcomes without a leader that can be trusted is the atomic commitment problem, and it is equivalent to consensus.

The standard reduction runs in the other direction: a total-order broadcast protocol can implement consensus by broadcasting a proposed value and delivering the first value in the agreed order. Because the two problems reduce to each other, any total-order broadcast protocol inherits the failure assumptions of consensus. It cannot be both available and consistent under a partition; it needs a majority of the replicas to make progress; and it needs a leader election or an equivalent mechanism to survive a sequencer failure.

Practical systems therefore implement total-order broadcast by running a consensus protocol over the log. The log’s index is the sequence number, and the consensus protocol decides which message occupies each index. The sequencer role becomes the leader role, and the leader’s failure is handled by the same election machinery that handles any other leader failure. This is the structure of replicated logs in the Raft family and of the multi-Paxos variants, and the details of the agreement protocols belong to the consensus cluster rather than here.

Batching and the latency-throughput trade

A sequencer that forwards one message per round trip pays a full network round trip per message. A sequencer that batches waits a short interval, accumulates the messages that arrive, assigns them a contiguous range of sequence numbers, and forwards the batch. The replicas deliver the batch in order, and the per-message cost amortizes the fixed cost of the network exchange.

Batching trades latency for throughput along a specific axis. The batch interval sets a floor on latency: a message that arrives just after a batch is closed waits for the next one. A longer interval admits more messages per batch and raises throughput, and it raises the worst-case delay for any individual message. The tuning point is a property of the workload, and it is why a log service exposes a knob rather than a fixed value.

The order within a batch is chosen by the sequencer and must be consistent. A sequencer that sorts a batch by client identifier, or by arrival time at the sequencer, produces a deterministic order that all replicas can reproduce from the batch contents. A sequencer that lets each replica order the batch independently defeats the purpose, because two replicas can then apply the same set of messages in different orders and diverge.

The cost of a single order

Total order is a strong guarantee, and the price is visible in three places.

The first is availability. A total-order service needs a quorum to make progress, so a partition that leaves a minority isolated stops the service for that minority. This is a deliberate choice: the alternative, allowing the minority to keep ordering, permits two divergent orders that cannot be reconciled without losing one of them.

The second is latency. Every message must reach the sequencer and then reach the replicas, and a consensus round adds at least one more exchange. A causally ordered broadcast can be delivered as soon as the dependencies computed by vector clocks are satisfied, which may be sooner than the total order is known. A system that needs only causal order should not pay for total order.

The third is the serialization of independent work. Two writes to unrelated keys must still be ordered relative to each other, and the sequencer processes them one at a time. Sharding the log by key restores parallelism and gives up the global order; the result is per-shard total order, which is the model of a partitioned log. The choice between one global order and many independent orders is a design decision that the ordering mechanism cannot make on its own.

The abstraction is nonetheless the right primitive for replicated state machines, because a deterministic state machine applied to a totally ordered log produces identical states at every replica by construction. The log is the order, and the order is the state. Everything else in a replicated system is an optimization around that fact.