Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Distributed Systems Theory

System Design HLD-08.08

Membership, gossip and failure detection

How clusters know who is alive: heartbeats and timeouts, phi accrual failure detectors, gossip that spreads news in log N rounds, and the SWIM protocol.

Advanced 10 min Last reviewed

The big idea

Every cluster has to answer a deceptively simple question all the time: who is in the cluster, and who is still alive? A database needs it to route reads away from a dead replica, a cache ring needs it to move keys ( Consistent hashing ), and a leader election needs it to know when to start ( Quorums and leader election ). This shared view is called membershipThe list of nodes currently in a cluster and their status (alive, suspected, dead, left), as each node believes it to be..

You cannot know for certain that a remote node is dead; you can only notice that you have not heard from it. A failure detectorA component that decides, from missing or late messages, which nodes are probably down. turns that silence into a verdict, and every detector trades speed against false alarms. Then the verdict has to reach everyone, and with hundreds or thousands of nodes no single node should have to tell everybody.

Think of how news spreads through an office. Nobody sends an email to all 500 people; each person mentions it to a couple of colleagues at lunch, and they each mention it to a couple more. By the end of the day, everyone knows, and no one person did much work. That is gossip.

How it works

Step 1: Heartbeats and timeouts

The simplest detector: each node sends a small heartbeatA periodic 'I am alive' message sent by a node so others can notice when it stops. every second, and if you miss heartbeats for, say, 5 seconds, you declare the node dead.

The timeout is the whole game. Too short, and a garbage collection pause or a congested link gets a healthy node evicted, triggering pointless failovers and data movement. Too long, and requests keep going to a dead node for that whole window. And sending heartbeats from everyone to everyone does not scale: with 1,000 nodes that is 1,000 x 999, about a million messages every second, just to say "still here".

Step 2: Phi accrual: suspicion as a number

A fixed timeout ignores that networks differ. A node across an ocean with jittery latency needs a longer window than one in the same rack. The phi accrual failure detectorA failure detector that outputs a continuous suspicion level (phi) based on the observed distribution of heartbeat arrival times, instead of a yes/no timeout. learns from history. It records the gaps between recent heartbeats and, at any moment, asks: given those past gaps, how unlikely is it that the next heartbeat is still coming?

Here is the probability, from the learned distribution, that a heartbeat arrives even later than the time already waited. If heartbeats normally arrive every 1.0 s give or take 0.1 s, then 1.3 s of silence is already very unlikely and phi climbs fast. If they normally wobble between 0.5 s and 3 s, phi rises slowly. Phi of 1 means about a 10 percent chance you are wrong if you declare the node dead now, phi of 2 means 1 percent, phi of 3 means 0.1 percent. Each application picks a threshold, so one detector serves both "fail over fast" and "never evict by mistake" users. Cassandra and Akka use phi accrual detectors.

Step 3: Gossip dissemination

Once a node notices something (a new member joined, node 17 looks dead), the news has to spread. In a gossip protocolA protocol where each node periodically exchanges information with a few randomly chosen peers, so updates spread through the cluster like an epidemic., every node, once per round, picks a few random peers and exchanges what it knows. The number of peers is the fan-outHow many peers each node contacts per gossip round..

A rumor spreading by gossip across a grid of nodes Fifteen nodes in a grid. In round 0 only the center node knows a rumor. In round 1 it tells two random peers. In round 2 each of the three informed nodes tells two more, reaching seven. The remaining nodes are still dark and will hear in the next round. r0 r1 r1 r2 r2 r2 r2 Figure 1. Gossip with fan-out 2. One node knows in round 0, three in round 1, seven in round 2. The informed set roughly triples each round until almost everyone knows. Step through the rounds.
  1. Round 0 Only the center node knows the news (it noticed a node fail, or a new member joined).
  2. Round 1 It tells two peers chosen at random. Three nodes now know.
  3. Round 2 Each informed node tells two random peers. Seven nodes know; one more round reaches nearly everyone.

The arithmetic is why gossip is so popular. While few nodes know, the informed set multiplies every round: with fan-out 2, roughly 1, 3, 9, 27... So the number of rounds to reach everyone grows with the logarithm of the cluster size, not with the size itself. Going from 100 nodes to 10,000 adds only a handful of rounds. Each node does a constant amount of work per round no matter how big the cluster is, there is no central coordinator to fail, and because peers are random, a few lost messages or dead nodes barely slow it down.

The cost is that news is eventually everywhere, not instantly: membership is an eventually consistent view ( PACELC and consistency models ). Nodes may briefly disagree about who is alive. Systems handle this by versioning each node's state (a heartbeat counter or generation number) so newer information always wins when two views meet.

Step 4: SWIM, detection and dissemination together

SWIMScalable Weakly-consistent Infection-style process group Membership: a protocol that detects failures with direct and indirect pings and spreads membership changes by piggybacking them on those pings. combines a scalable detector with gossip:

  1. Ping: each period, a node pings one random member and waits for an ack.
  2. Indirect ping: if no ack arrives, it asks k other members to ping that node on its behalf (ping-req). This tells "the target is down" apart from "the link between me and the target is flaky".
  3. Suspect, then confirm: if no one gets an answer, the target is marked suspect rather than dead. If it is alive, it hears the suspicion through gossip and refutes it with a higher incarnation number. If not, after a timeout it is declared dead.
  4. Piggyback: membership updates ride along on the ping and ack messages already being sent, so dissemination costs no extra messages.

Each node sends a constant number of messages per period regardless of cluster size, unlike all-to-all heartbeats. HashiCorp's memberlist library, used by Consul and Serf, is based on SWIM with extensions.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Leave fan-out at 2 and press Play. Watch the S-shaped curve: slow at first, explosive in the middle, slow again at the end as informed nodes keep picking peers who already know.
  2. Set fan-out to 1 and play again. It still reaches everyone, just in more rounds. Compare the round count with log2(100), about 6.6.
  3. Set fan-out to 5. It finishes in fewer rounds, but count the cost: most of the extra messages in the last rounds go to nodes that already knew.

Going deeper

Why the tail is slow

Near the end, most random picks hit nodes that already know, so the last few stragglers take a while. Real protocols mix strategies: push (tell peers what you know) is fast early, pull (ask peers what they know) is fast late, and push-pull does both in one exchange. Many systems also gossip more often to a node that seems to be missing updates.

False positives cost more than slow detection

Declaring a live node dead is expensive: data gets re-replicated, leaders change, clients reconnect. That is why SWIM uses a suspect state and why phi thresholds are usually set conservatively. A node that keeps flapping between alive and dead can hurt a cluster more than one that is simply down.

Trade-offs

OptionWins whenLoses when
All-to-all heartbeats with fixed timeout Small clusters (a handful of nodes) where simplicity matters most Scale (messages grow with N squared) and links with variable latency
Phi accrual detector Networks with uneven latency; tunable trade-off between speed and false alarms Needs heartbeat history; a new or rarely heard node has little to learn from
Gossip dissemination Large clusters with no central coordinator; robust to lost messages News is eventually consistent and takes several rounds to spread
Central coordinator (etcd, ZooKeeper sessions) A single authoritative membership view for leader election and locks The coordinator becomes a dependency and a scaling limit

Common mistakes

  • Setting failure timeouts shorter than garbage collection pauses, so healthy nodes get evicted.
  • Treating a gossip membership view as instantly consistent and acting on it as if every node agrees.
  • Declaring a node dead from one missed ping instead of using indirect checks and a suspect state.
  • Running all-to-all heartbeats on hundreds of nodes and wondering where the network bandwidth went.
  • Using gossip membership alone for decisions that need exactly one owner; use consensus for those ( Consensus: Raft ).

In the wild

Cassandra nodes gossip their state with random peers every second and use a phi accrual detector to mark peers down. Consul and Serf build cluster membership on HashiCorp's memberlist, a SWIM-based library. Akka Cluster uses gossip for membership and phi accrual for failure detection, and Amazon's Dynamo paper described gossip-based membership and failure detection for its storage nodes.

Check yourself

  1. Why can't a failure detector be both instant and never wrong?

    Show answer

    B. Because a slow node and a dead node look the same from outside, so faster verdicts mean more false alarms Silence is ambiguous. Waiting longer reduces mistakes but delays detection; every detector picks a point on that curve.

  2. A phi accrual detector reports phi = 3 for a node. Roughly what does that mean?

    Show answer

    B. If you declare it dead now, there is about a 0.1 percent chance you are wrong Phi is minus log10 of the probability that a heartbeat still arrives later, so phi 3 means about 1 in 1,000.

  3. A cluster grows from 100 to 10,000 nodes. Roughly how does the number of gossip rounds to spread news change?

    Show answer

    B. It roughly doubles, since rounds grow with log N log of 10,000 is twice the log of 100, so a few more rounds, while each node still sends a constant number of messages per round.

  4. In SWIM, why ask other members to ping a node that did not answer?

    Show answer

    B. To tell a dead node apart from a broken link between the two nodes If others can reach it, the problem is the path, not the node, and it should not be declared dead.

Recap

  • Membership is each node's view of who is in the cluster and alive.
  • Failure detectors turn silence into a verdict and always trade detection speed against false alarms.
  • Phi accrual detectors learn heartbeat timing and output a suspicion level you threshold.
  • Gossip spreads news in a logarithmic number of rounds with constant work per node and no coordinator.
  • SWIM combines random pings, indirect pings, a suspect state and piggybacked gossip.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy