Gossip & Failure Detection

Heartbeats vs gossip, phi-accrual and SWIM detectors, cluster membership, and when to use a coordinator instead.

In a cluster of hundreds of nodes, every node needs to know two things: who is in the cluster and who is alive right now. There are two ways to answer that — ask a central coordinator, or let nodes tell each other. Gossip protocols are the second way: each node periodically swaps what it knows with a few random peers, and news spreads through the cluster like a rumor. It comes up whenever you design a leaderless, Dynamo-style system (key-value store, Cassandra, a distributed cache) and the interviewer asks, "how do nodes know a peer died?"

Failure detection is guesswork

A node can't tell a crashed peer from a slow one or a broken network link — all three look like silence. So every failure detector is a timeout tuned between two mistakes:

Too short — a GC pause or a network blip marks a healthy node dead, triggering needless failovers and data movement.
Too long — a really dead node keeps receiving traffic and the system stays degraded for longer.

That's why detectors only ever suspect a node. What the system does with a suspicion (stop routing to it, promote a replica, re-replicate its data) is a separate decision, and the expensive actions should wait longer than the cheap ones.

Heartbeats: the simple version

Each node sends "I'm alive" to a monitor every second; after a few missed beats, the monitor declares it dead. This works well at small scale and is what leader-based systems use — followers in Raft watch the leader's heartbeats, and a ZooKeeper or etcd session expires when its client stops sending them.

The problems appear as the cluster grows:

All-to-all heartbeats cost O(N²) messages per interval — 1,000 nodes means a million messages a second.
A central monitor is a bottleneck and a single point of failure, and it only sees the network from where it sits.

How gossip works

Every round (typically once a second), each node picks one to three random peers and exchanges its view of the cluster: for every node it knows, a heartbeat counter and a version. Each side keeps the newer entry for every node, so after the exchange both know whatever either knew.

[Node A: picks random peer] -> [Sends digest: node → version] -> [Node B: replies with newer entries + what it lacks] -> [Both merge, newest version wins]

It spreads fast. Like an epidemic, the number of informed nodes roughly multiplies each round, so news reaches all N nodes in O(log N) rounds — a 1,000-node cluster converges in around ten seconds.
The load is flat. Each node sends a constant number of messages per round no matter how big the cluster is.
It's robust. There's no special node; losing messages or whole nodes only slows things down slightly, because the information takes other paths.
It's eventually consistent. At any instant, different nodes can briefly disagree about who is up.

Exchanging digests (node → version) first and sending full state only for entries that differ keeps messages small. Even so, the state each node holds grows with N, which is one reason gossip clusters top out in the low thousands of nodes.

Failure detection falls out naturally: every node keeps bumping its own heartbeat counter, gossip carries it around, and if a node's counter stops increasing for long enough, everyone gradually concludes it's down — without anyone pinging it directly.

Smarter detectors

Phi-accrual

Instead of a fixed timeout, each node tracks the history of heartbeat arrival gaps for each peer and computes phi — how unlikely the current silence is given that history. A peer that usually checks in every 1 s and has gone quiet for 5 s gets a high phi; a peer on a jittery link whose gaps vary a lot needs a longer silence to reach the same score. The node is suspected when phi crosses a threshold (Cassandra's default is 8). One knob adapts to each link instead of one timeout for every link. Cassandra and Akka use it.

SWIM

SWIM (Scalable Weakly-consistent Infection-style Membership) separates detecting a failure from spreading the news:

Each period, a node pings one random member.
No ack? It asks k other members to ping it indirectly. This rules out a broken link between just those two nodes.
Still nothing: the member is marked suspect, not dead. That status rides along on normal ping traffic (piggybacking), so there are no extra messages.
A suspected node that's actually alive refutes it by announcing a higher incarnation number; if nobody hears a refutation before the suspicion timeout, it's declared dead.

Message load per node stays constant, and the suspicion step cuts false positives sharply. HashiCorp's memberlist (behind Consul and Nomad) is built on SWIM.

What else rides on gossip

Once there's a cheap channel that reaches every node, systems use it for other small, slowly changing cluster state:

Membership changes — joins, leaves and the consistent hashing ring (which node owns which token ranges), so any node can route a request.
Node metadata — load, schema version, data center and rack.
Bootstrapping — a new node contacts a few configured seed nodes to join the gossip and learn the cluster.

Bulk data doesn't travel by gossip. Repairing replica *data* is done by anti-entropy — replicas compare Merkle trees and sync only the ranges that differ (see Replication). It's the same idea of background reconciliation, but run point-to-point between the replicas of a range.

Gossip vs. a coordinator

This is the real interview decision: decentralized, eventually consistent membership, or strongly consistent membership from consensus.

Many real systems use both: gossip for "who's around and healthy" and consensus for decisions that must never conflict. Consul gossips membership across every agent but stores its catalog with Raft. Redis Cluster gossips health, but a node is only marked failed once a majority of primaries agree it's unreachable.

[!WARNING] Gossip can't safely elect a leader Two nodes with different views of who is alive can each decide they should own the same partition. If exactly one owner matters — leader election, locks, ownership of a shard — use consensus or a coordination service with fencing tokens. Leaderless designs avoid the problem by not needing a single owner: quorums and conflict resolution handle concurrent writes.

Where you'll use it in a design

Leaderless key-value stores — gossip membership and the ring, phi-accrual detection, plus hinted handoff for writes to a replica that's briefly down. See Design a Distributed Key-Value Store.
Cache and storage clusters — clients or routers learn the current node list from gossip and stop sending requests to suspect nodes.
Service discovery — agents on every host gossip health so a service's instance list stays current without a central bottleneck.

[!TIP] Separate "suspect" from "remove" Stop routing to a suspected node within seconds, but wait minutes (or an operator) before re-replicating its data. Most "failures" are restarts and blips, and moving terabytes for a node that comes back in 30 seconds causes more damage than the outage itself.

[!INTERVIEW] Explaining failure detection "Every node gossips once a second with a couple of random peers, exchanging heartbeat counters for the whole cluster, so membership and the ring converge in a few seconds with no central component. Each node runs a phi-accrual detector, so a node with a jittery link isn't flagged as quickly as a dead one. Suspected nodes stop getting reads and writes, and hinted handoff covers their writes. We only re-replicate if a node stays down past a longer timeout. Anything that needs a single owner, like a lock, goes through etcd instead."