Total order broadcast, also known as atomic broadcast, is a communication primitive that guarantees every node in a system delivers the same set of messages in the same order. If one node sees message A before message B, then every other node also sees A before B. This single guarantee, that all participants agree on one global sequence of messages, turns out to be remarkably powerful.
Its power comes from the connection to state-machine replication. Leslie Lamport’s 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System,” catalogued on his publications page, frames distributed computing in terms of implementing an arbitrary state machine across many nodes. If every replica starts in the same state and applies the same commands in the same order, every replica stays identical. Total order broadcast is exactly what feeds those commands to the replicas in a single agreed order.
Lamport’s paper supplies the underlying machinery for ordering: it defines the happens-before relation, a partial order on events, and shows how logical timestamps can extend that partial order into a consistent total order. That construction is the conceptual root of how a distributed system can agree on a sequence of events without a shared physical clock.
Total order broadcast is equivalent in power to consensus: solving one lets you solve the other. That equivalence is why total order broadcast inherits the same fundamental difficulty as agreement in distributed systems, and why protocols that implement it sit at the heart of fault-tolerant replicated services.