Reliable Broadcast

Imagine a general sending battle orders to five commanders. She manages to radio three of them before her radio breaks. The other two receive nothing. Now three commanders attack and two hold back — a disaster born not from treachery but from a simple crash.

Reliable broadcast is the distributed-systems answer to this problem. It is a communication abstraction that provides one guarantee: if any correct node delivers a message, then every correct node eventually delivers it. Equivalently, if the sender crashes before any node delivers, then no node delivers.

The guarantee sounds modest — nothing about when delivery happens, only about whether all nodes agree on having received the message. Yet that modest guarantee is surprisingly hard to achieve, and it sits at the foundation of nearly every fault-tolerant distributed system built today. It is the stepping stone toward stronger primitives like atomic broadcast and the bedrock of consensus.

The simulation below has one sender (node S) and four receivers (nodes A–D). When S broadcasts, it sends the message to each receiver in sequence. You can choose whether S crashes before it finishes. Without crash recovery, some nodes would miss the message. With reliable broadcast, the first node that receives the message relays it to everyone else — so every correct node delivers, or none does.

<!-- {{c_html_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label class="toggle-label">
    <input type="checkbox" id="crash-toggle">
    <span>{{crash_label}}</span>
  </label>
  <select id="crash-after">
    <option value="0">{{crash_after_0}}</option>
    <option value="1">{{crash_after_1}}</option>
    <option value="2">{{crash_after_2}}</option>
  </select>
</div>
<div id="network" class="network"></div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .8rem; margin-bottom: .8rem; flex-wrap: wrap; }
.toggle-label { display: flex; align-items: center; gap: .4rem; font-size: .9rem; cursor: pointer; user-select: none; }
select { font: 14px system-ui; padding: .3rem .5rem; border: 1px solid #aaa; border-radius: 6px; }
.network { display: flex; gap: 1rem; align-items: flex-start; margin: .4rem 0 .8rem; flex-wrap: wrap; }
.node-wrap { display: flex; flex-direction: column; align-items: center; gap: .3rem; }
.node { width: 52px; height: 52px; border-radius: 50%; display: flex; align-items: center; justify-content: center;
        font: 700 16px ui-monospace, monospace; border: 2px solid #8898aa; background: #e8eef3;
        transition: background .25s, border-color .25s; position: relative; }
.node.sender { border-color: #1d3557; background: #1d3557; color: #fff; }
.node.delivered { background: #0a7d33; border-color: #065a24; color: #fff; }
.node.crashed { background: #c92f3c; border-color: #a52331; color: #fff; opacity: .75; }
.node.relaying { background: #f4a261; border-color: #e07b34; color: #fff; }
.node-label { font-size: .78rem; color: #555; text-align: center; min-height: 1.1em; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: not-allowed; }

// Code not found

Notice the key asymmetry: a relay costs just one extra round of messages, but it turns an unreliable sender into a guarantee. If S crashes after delivering to A alone, A immediately relays to B, C, and D. No node is left out.

How hard is reliable broadcast, really? It depends on the failure model.

• Crash failures only. Each node either works correctly or stops forever — no lying, no sending garbage. Under this model, reliable broadcast has been solved since the 1980s. The classic algorithm by Bracha and Toueg (1985) uses $O(n^2)$ messages and tolerates up to $f < n/2$ crash failures among $n$ nodes. The insight: each node that receives the message re-sends it to all others before delivering. This single relay step is enough.
• Byzantine failures. Now nodes can crash, lie, send different messages to different peers, or behave arbitrarily. Reliable broadcast still exists — Bracha's 1987 protocol achieves it with $O(n^2)$ messages — but it requires at least $n > 3f$ nodes to tolerate $f$ Byzantine faults. The cost is higher: nodes must collect echo and ready messages from a quorum before they dare deliver.
• Lower bounds. Any reliable broadcast protocol for $n$ nodes must send $\Omega(n)$ messages in the worst case: the sender alone cannot reach everyone without help, so at least $n - 1$ additional transmissions are needed.

Reliable broadcast is decidable and efficient for crash faults, unlike the undecidable halting problem. The hard boundary arrives only when you demand total order on delivery — that is the transition from reliable broadcast to consensus, where impossibility results like FLP kick in.

Reliable broadcast is the quiet workhorse of distributed computing. You rarely see it named directly, but it hides inside almost every fault-tolerant system:

• Database replication: a primary crashes after writing to two replicas but not the others. Reliable broadcast ensures either all replicas apply the write or none do, preventing split state.
• Blockchain gossip: when a miner broadcasts a new block, the protocol must ensure all honest nodes eventually receive it — even if the miner goes offline immediately after sending to a few peers.
• Distributed logs (Kafka, Pulsar): the leader publishes a record; if it crashes, followers must agree on whether the record was committed or not, using a reliable-broadcast-like relay step.
• Atomic commit in databases: the coordinator sends a commit decision; every participant must learn of it, or the transaction must roll back everywhere — the same all-or-nothing flavor as reliable broadcast.

Once you have reliable broadcast, you can compose it into consensus protocols and from there into full state-machine replication — the engine behind Raft, Paxos, and every cloud database that promises durability.

Reliable broadcast solves a simple-sounding problem elegantly: if one correct node delivers a message, every correct node delivers it. The trick is a relay — each recipient becomes a co-sender, flooding the message onward before anyone commits to delivering it. A sender crash becomes harmless; the network itself carries the message to completion.

The protocol is efficient ($O(n^2)$ messages), proven correct, and practically ubiquitous — you will find its logic inside every replicated database, blockchain node, and distributed log you rely on daily. And it is the first rung on the ladder that climbs toward consensus: once every correct node is guaranteed to see the same set of messages, agreeing on their order is the next — and harder — challenge.