The Chandra–Toueg Algorithm

Imagine five friends trying to pick one restaurant over a group chat. People drop offline mid-conversation. Messages arrive late. Nobody can tell whether Nandana left or is just slow to type. And yet — somehow — the group has to end up at exactly one restaurant, with nobody walking into a different door.

That, stripped of the food, is the consensus problem. The Chandra–Toueg algorithm (1996) is a famous, elegant way to actually solve it when computers can crash. It shares its core ideas — a leader, majority quorums, “freshest value wins” — with Paxos and Raft, the protocols running inside basically every serious distributed database today. (Paxos was developed independently around the same time, not derived from it — they’re siblings, not parent and child.)

1. Why agreement is secretly hard

There’s a famous result — the FLP impossibility (Fischer, Lynch, Paterson) — that says something brutal:

In a purely asynchronous system where even one computer can crash, there is no algorithm that is guaranteed to reach agreement and always finish.

ELI5 version: in the group chat, if Nandana goes silent, you genuinely cannot tell whether she crashed or is just lagging. If you wait for her, you might wait forever (she crashed). If you give up on her, she might’ve been about to send the deciding vote (she was just slow). Either choice can go wrong. There’s no perfect move. That’s FLP.

So how does anything work in real life? We cheat — legally.

2. The cheat: a failure detector (◊S)

Instead of trying to answer “dead or slow?” inside the agreement logic, we hand that messy job to a separate gadget called a failure detector. Think of it as a slightly unreliable rumor mill: each computer asks it “who do you suspect is down?” and gets back a list of names.

The detector is allowed to be wrong — but only in two carefully limited ways. The version Chandra–Toueg needs is called ◊S (“eventually strong”):

• Strong completeness — every truly-crashed computer is eventually suspected by everyone, forever. → A dead node can’t hide; we’ll never wait on a corpse indefinitely.
• Eventual weak accuracy — eventually, at least one still-alive computer stops being wrongly suspected by anyone. → Eventually there’s someone everyone trusts, so progress becomes possible.

◊S is equivalent to ◊W and to Ω (the “eventually one stable leader” oracle) when channels are reliable — and ◊W/Ω is the provably weakest failure detector that can solve consensus, provided a majority of nodes stay correct. In practice you implement ◊S with timeouts — if you haven’t heard a heartbeat in a while, you “suspect.” (Raft’s election timeout is literally this.)

3. Test it — why a majority always overlaps

Before the algorithm, one idea you have to feel in your bones: any two groups that each contain more than half the nodes must share at least one member. That shared member is how a decision survives from one round to the next.

Drag the slider. Quorum A is the left group, Quorum B is the right group — both are majorities. Watch the dark overlap node that they’re forced to share.

4. The plan: a rotating chairperson

The algorithm runs in numbered rounds. Each round has one pre-assigned coordinator (the chairperson), chosen round-robin:

coordinator(round) = round mod N      // 0,1,2,...,N-1,0,1,2,...

The chairperson’s job each round: collect everyone’s current vote, pick one value, and try to get a majority to lock it in. If that works, everyone agrees and we’re done. If the chairperson crashes — or the rumor mill suspects it — the others give up on this round and rotate to the next chairperson.

Because the detector is eventually accurate, the rotation will eventually land on a chairperson that nobody wrongly suspects. That round finishes. Done.

The four phases of a round (ELI5)

1. Everyone → chairperson: “here’s my current vote, and how recently I changed it” (the timestamp).
2. Chairperson decides what to propose: it waits to hear from a majority, then picks the vote with the most recent timestamp and announces “let’s all go with this.”
3. Everyone replies: each node either adopts the proposal and says ACK, or — if the rumor mill says the chairperson looks dead — it says NACK and bails out of the round.
4. Chairperson tallies: if a majority said ACK, the value is locked → it shouts DECIDE! and everyone who hears it commits and stops. Otherwise, no decision; rotate to the next round.

5. Test it — run the consensus yourself

Below is a live, simplified Chandra–Toueg cluster. Each card is a node with a vote (0 or 1) and a timestamp (ts). The ★ marks the current round’s chairperson.

• Run round → advance one round of the rotating chairperson.
• Click a node → crash or revive it (a corpse, or a node that came back).
• Click a node’s value chip → flip its vote (before anyone decides).
• “falsely suspect” → simulate the rumor mill lying about a healthy chairperson for one round, so you can watch a round get wasted without the cluster ever deciding something wrong.

Try this: crash the node about to be chairperson, hit Run round, and watch it rotate past the corpse. Or crash a majority and see it correctly refuse to decide.

6. Why it’s always safe (even when the rumor mill lies)

Safety = “never two different answers, never an invented one.” This holds no matter how badly ◊S misbehaves.

• Agreement: once value v is locked by a majority in some round, §3’s overlap means every later chairperson sees v carrying the freshest timestamp, and §4’s rule forces it to re-propose v. No second value can ever win.
• Validity: the proposed value is always someone’s actual starting vote — nothing is fabricated.

A lying detector can cause wasted rounds and false alarms, but it can never make two nodes decide differently. The detector affects only how fast we finish, never whether we’re correct. (You can prove this to yourself in §5: tick “falsely suspect” as many times as you like — rounds get burned, but the eventual decision is still single and valid.)

7. Why it eventually finishes (liveness)

Termination needs both ◊S guarantees working together:

• Strong completeness → a crashed chairperson is eventually suspected, so no round hangs forever waiting on a dead node. The cluster always moves on.
• Eventual weak accuracy → eventually some live node stops being wrongly suspected. When the rotation reaches that node’s turn, nobody bails, a majority ACKs, and DECIDE fires.

8. The family resemblance: Paxos & Raft

Chandra–Toueg is the theory; Paxos and Raft are what you actually deploy. They’re the same idea in different clothes:

9. TL;DR

• Solves consensus despite crashes by adding a ◊S “maybe-dead” detector to an almost-asynchronous system.
• A rotating chairperson drives rounds; nodes abandon a round the moment the detector suspects the chairperson.
• Majority quorums + freshest-timestamp-wins make safety unconditional — no two different answers, ever, no matter how much the detector lies.
• Finishing is only eventual — guaranteed once the detector calms down. Until then FLP still applies, but for a finite time.
• Needs a correct majority (f < n/2), crash-only failures, reliable channels.
• It shares the same core machinery as Paxos and Raft (developed independently, same era) — leader, quorums, freshest-value-wins.