Introduction

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.

Try It

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.

<!-- Reliable broadcast demo — sender S, receivers A-D; optional crash mid-broadcast -->
<p class="hint">Node S broadcasts a message to receivers A, B, C, D one by one. Toggle the crash to see what happens when S fails partway through. With reliable broadcast, the first receiver that got the message <b>relays</b> it to the rest — so all correct nodes deliver, or none do.</p>
<div class="controls">
  <label class="toggle-label">
    <input type="checkbox" id="crash-toggle">
    <span>S crashes after delivering to:</span>
  </label>
  <select id="crash-after">
    <option value="0">0 nodes (before any delivery)</option>
    <option value="1">1 node (A only)</option>
    <option value="2">2 nodes (A and B)</option>
  </select>
</div>
<div id="network" class="network"></div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="run" type="button">Broadcast</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the reliable-broadcast demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Reliable broadcast: all-or-nothing delivery even when sender crashes.
// Protocol: sender sends to each receiver; first receiver re-broadcasts to all.

const NODES = ['S', 'A', 'B', 'C', 'D'];
// S = sender, A-D = receivers
// S = sender, A-D = receivers

let animating = false;

function getState() {
  // read UI controls
  return {
    crash: document.getElementById('crash-toggle').checked,
    crashAfter: parseInt(document.getElementById('crash-after').value, 10)
  };
}

function buildNetwork() {
  // create visual nodes
  const net = document.getElementById('network');
  net.innerHTML = '';
  NODES.forEach(id => {
    const wrap = document.createElement('div');
    wrap.className = 'node-wrap';
    const node = document.createElement('div');
    node.id = 'node-' + id;
    node.className = 'node' + (id === 'S' ? ' sender' : '');
    node.textContent = id;
    const lbl = document.createElement('div');
    lbl.id = 'label-' + id;
    lbl.className = 'node-label';
    lbl.textContent = id === 'S' ? 'sender' : 'waiting';
    wrap.appendChild(node);
    wrap.appendChild(lbl);
    net.appendChild(wrap);
  });
}

function setNode(id, cls, lbl) {
  // update a node's visual state and label
  const n = document.getElementById('node-' + id);
  n.className = 'node ' + cls;
  document.getElementById('label-' + id).textContent = lbl;
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function delay(ms) { return new Promise(r => setTimeout(r, ms)); }

async function runBroadcast() {
  if (animating) return;
  animating = true;
  document.getElementById('run').disabled = true;
  const { crash, crashAfter } = getState();
  // list of receiver node IDs
  const receivers = ['A', 'B', 'C', 'D'];
  let delivered = 0;

  setStatus('Broadcasting…', 'info');

  // Phase 1 — sender S delivers to each receiver one by one
  // Phase 1: sender S delivers to each receiver one by one
  for (let i = 0; i < receivers.length; i++) {
    const r = receivers[i];
    if (crash && i === crashAfter) {
      // sender crashes here
      setNode('S', 'crashed', 'CRASHED');
      setStatus(i18nFmt('S crashed after %n% deliveries — starting relay.', { n: delivered }), 'bad');
      break;
    }
    await delay(600);
    setNode(r, 'delivered', 'delivered');
    delivered++;
    setStatus(i18nFmt('Delivered to %n% node(s)…', { n: delivered }), 'info');
  }

  if (!crash || crashAfter >= receivers.length) {
    // Sender did not crash — all delivered directly
    // Sender did not crash — all delivered directly
    setNode('S', 'sender', 'sender');
    setStatus('All nodes delivered directly.', 'ok');
    animating = false;
    document.getElementById('run').disabled = false;
    return;
  }

  // Relay phase — any node that already received re-broadcasts to the rest
  // Relay phase: any node that already received re-broadcasts to the rest
  const haveMessage = receivers.slice(0, crashAfter);
  const missing = receivers.slice(crashAfter);

  if (haveMessage.length === 0) {
    // No one received anything — nothing to deliver anywhere
    // No one received anything; nothing to deliver anywhere
    setStatus('S crashed before any delivery — no node delivers (safe).', 'bad');
    animating = false;
    document.getElementById('run').disabled = false;
    return;
  }

  // Mark first receiver as relaying
  // Mark first receiver as relaying
  setNode(haveMessage[0], 'relaying', 'relaying');
  setStatus('A node received the message and is relaying to the rest…', 'info');
  await delay(700);

  // Relay delivers to missing nodes
  // Relay delivers to missing nodes
  for (const r of missing) {
    await delay(500);
    setNode(r, 'delivered', 'delivered');
  }
  // All nodes that had the message keep it
  // All nodes that had the message also keep it
  setNode(haveMessage[0], 'delivered', 'delivered');
  for (const r of haveMessage.slice(1)) {
    setNode(r, 'delivered', 'delivered');
  }
  setStatus('All correct nodes delivered via relay.', 'ok');
  animating = false;
  document.getElementById('run').disabled = false;
}

function resetSim() {
  // reset the simulation to initial state
  animating = false;
  document.getElementById('run').disabled = false;
  buildNetwork();
  setStatus('', '');
}

document.getElementById('run').addEventListener('click', runBroadcast);
document.getElementById('reset').addEventListener('click', resetSim);
document.getElementById('crash-toggle').addEventListener('change', resetSim);
document.getElementById('crash-after').addEventListener('change', resetSim);
buildNetwork();
Result
Console

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.

The Real Complexity

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(n2)O(n^2) messages and tolerates up to f<n/2f < n/2 crash failures among nn 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(n2)O(n^2) messages — but it requires at least n>3fn > 3f nodes to tolerate ff 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 nn nodes must send Ω(n)\Omega(n) messages in the worst case: the sender alone cannot reach everyone without help, so at least n−1n - 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.

Where It Matters

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.

Conclusion

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(n2)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/reliable-broadcast/Content licensed under CC BY-NC 4.0.