Questions: Total Order Broadcast and Strong Consistency

Question 1

Two nodes both deliver messages M1 and M2, which were sent concurrently (no causal relationship). Under causal broadcast, which of the following is possible?

• A. Node A delivers M1 then M2, while Node B delivers M2 then M1 — causal broadcast permits this
• B. Node A delivers M1 then M2, while Node B delivers M2 then M1 — causal broadcast forbids this
• C. Both nodes are guaranteed to deliver M1 before M2 regardless of which arrived first
• D. Concurrent messages are buffered until a causal ordering can be determined

Answer: (A)

Causal broadcast only enforces that causally related messages are delivered in causal order. Concurrent messages — those with no happened-before relationship — have no mandated order, so different nodes can legitimately deliver them in different sequences. Total order broadcast is specifically designed to prevent this: it guarantees all correct nodes deliver all messages in the same sequence, even concurrent ones. This distinction matters enormously for replicated state machines, where different delivery orders can produce different final states.

Question 2

Why does a coordinator-based implementation of total order broadcast have a fundamental limitation even when the coordinator is working correctly?

• A. Coordinators can only handle binary messages, not arbitrary data
• B. The coordinator is a bottleneck — all messages must pass through it — and a single point of failure that requires consensus to replace
• C. A coordinator can only assign sequence numbers to messages it generated itself, not to messages from other nodes
• D. Coordinator-based systems violate the reliability property because the coordinator may drop messages

Answer: (B)

Every message must be routed through the coordinator for sequencing before delivery, making the coordinator a throughput bottleneck regardless of how fast the rest of the network is. More critically, if the coordinator crashes, the system stalls. Electing a new coordinator safely — without losing, duplicating, or reordering messages — is itself a consensus problem. So even the simple coordinator approach secretly depends on consensus for fault tolerance, revealing the deep connection between total order broadcast and consensus.

Question 3

Total order broadcast and consensus are computationally equivalent: given an algorithm for one, you can construct an algorithm for the other.

• T. True
• F. False

Answer: True

The equivalence works in both directions. Given consensus, you can build total order broadcast: use consensus to agree on the next message to deliver at each step of the sequence. Given total order broadcast, you can solve consensus: each process broadcasts its proposed value, and the first message delivered by all processes is the consensus decision. This equivalence means total order broadcast inherits all the theoretical properties and limitations of consensus — including FLP impossibility in purely asynchronous systems with crash failures.

Question 4

Because total order broadcast provides stronger ordering guarantees than causal broadcast, it is generally the preferred choice for distributed system design.

• T. True
• F. False

Answer: False

Stronger guarantees come with higher cost. Total order broadcast requires consensus, which cannot be implemented in a purely asynchronous system without timing assumptions, and practical implementations have throughput limitations due to the coordination overhead. Many applications — social media feeds, shopping carts, DNS caching — work correctly with causal or even weaker ordering guarantees and would suffer unnecessary performance penalties from total order. The right choice depends on what consistency the application actually requires, not the strongest guarantee available.

Question 5

Why does total order broadcast inherit the FLP impossibility result, and what does this mean for how systems like Raft and Paxos work in practice?

Model answer: FLP impossibility states that no deterministic algorithm can guarantee consensus (or equivalently, total order broadcast) in a purely asynchronous system where even one process can crash. Since total order broadcast is equivalent to consensus, it inherits this impossibility. Practical systems like Raft and Paxos escape the impossibility by making timing assumptions: they use leader election with timeouts (not pure asynchrony) and only guarantee progress when a majority of nodes is available and communicating within bounded delays. When those conditions fail, the system stalls rather than risk inconsistency — correctness is preserved, but liveness is not guaranteed.

The FLP result is often misunderstood as 'you cannot build reliable distributed systems.' It actually says you must choose between safety (never wrong) and liveness (always eventually decides) in an asynchronous model. Real systems choose safety and use timeouts/heartbeats to approximate liveness in practice. Total order broadcast highlights why strong consistency is fundamentally expensive: it is not a matter of clever engineering, but of computability.