Total Order Broadcast
Summary: A communication protocol that ensures all nodes in a distributed system receive the same messages in the same order.
Sources: chapter9
Last updated: 2026-04-17
Total order broadcast (also known as atomic broadcast) is a communication primitive for exchanging messages between nodes (source: chapter9, p. 348). It is equivalent to reaching consensus on the order of messages (source: chapter9, p. 350).
Properties
Total order broadcast requires two safety properties to be satisfied (source: chapter9, p. 348):
- Reliable delivery: If a message is delivered to one node, it is delivered to all nodes.
- Totally ordered delivery: Messages are delivered to every node in the same order.
Relationship to Consensus
Total order broadcast and consensus are equivalent (source: chapter9, p. 350).
- If you have total order broadcast, you can achieve consensus (e.g., by having each node propose a value as a message and the first message in the total order being the decided value) (source: chapter9, p. 350).
- If you have consensus, you can achieve total order broadcast (by running repeated rounds of consensus to decide on each message in a sequence) (source: chapter9, p. 366).
Use Cases
- Database Replication: If every message represents a write to the database and every replica processes the same writes in the same order, they will remain consistent. This is known as state machine replication (source: chapter9, p. 349).
- Serializability: Total order broadcast can be used to implement serializable transactions (source: chapter9, p. 349).
- Locking Services: It can be used to implement lock services that provide fencing-tokens (source: chapter9, p. 349).
Implementing Linearizability
While total order broadcast is asynchronous (guaranteeing that messages are delivered but not when they are delivered), it can be used to implement linearizability (source: chapter9, p. 350).
- For example, you can implement a linearizable compare-and-set operation by appending a message to the log and waiting for it to be delivered back to you (source: chapter9, p. 350).