Total-order (atomic) broadcast demands that every correct node deliver the same set of messages in the same order — even though messages arrive at each node in whatever order the network chooses. Give each message a sequence number from an agreed source and deliver strictly in sequence, and every node reconstructs one identical timeline. The deep fact: this is equivalent to consensus — solving either solves the other — so a replicated state machine and an agreement protocol are two faces of one problem.
Deliver the same messages to two nodes in scrambled arrival orders, but sort by sequence number — and both nodes reconstruct the identical delivery timeline, the property a replicated state machine needs to stay in lock-step: live demo
“Ordering messages consistently is easier than full consensus.” — it is exactly as hard. Chandra–Toueg proved total-order broadcast and consensus are equivalent: each can be built from the other. So the moment you can agree on one value, you can agree on a whole ordered log, and vice-versa. cited
Because ordered delivery equals consensus, the replicated state machine — feed identical ordered commands to identical machines and they stay identical — is the universal recipe for fault-tolerant services. One ordered log, many machines, one truth. Chandra–Toueg 1996
On the canonical compiler, messages numbered 1,2,3 arriving as [3,1,2] at one node and [1,2,3] at another both deliver in the identical order after sequencing: