Gossip Protocols and Failure Detection

That one server becomes a single point of failure for the truth. If its own network goes bad, it declares healthy nodes dead, and every client believes it. A gossip protocol removes that single judge.

Picture a common setup. A food delivery app keeps popular data in a 40-node cache cluster, so most reads skip the slow main database. A node is one server in the cluster. The setup is made up, but the problem is real.

The app's client library decides which node holds each key. To know which nodes were alive, the team first used one central health checker. It pinged every node once a second, and three missed replies marked a node dead.

Here is that first design. Look at the checker box. Every arrow about health starts there, so its view of the cluster is the only view anyone gets.

One Friday evening, the checker's own network card dropped packets for about 20 seconds. Replies from healthy nodes never reached it, so it marked 25 of the 40 nodes dead.

Clients moved those keys to the 15 survivors, which had none of that data. The cache hit rate, the share of reads found in the cache, fell from 95 percent to 40 percent. The database maxed out, and orders slowed for 12 minutes.

Nothing was down except the thing that decides what is down. The fix is to share the job of watching across every node, so no single box can be wrong for the whole cluster.

A gossip protocol is a way for nodes in a cluster to spread information by repeatedly telling a few randomly chosen peers what they know. Those peers pass it on, and soon every node knows.

Think of a morning walkers' group in a big city park. Nobody sends out a notice. Two walkers chat on one lap, then each chats with someone else on the next lap. By seven o'clock, the whole group knows the gate timings have changed.

Map it part by part. Each walker is a node, each lap is a round, each chat is one gossip message, and the gate news is a change such as a node joining. Nobody is in charge of the news, yet it still reaches almost everyone.

Where the picture breaks: nodes pick partners at random on a timer, not by who happens to walk nearby. And a silent walker is usually just elsewhere, while a silent node might be dead, slow or cut off.

Computer gossip works in rounds. A round is one tick of a timer, often one second. In each round, every node picks a random peer, and the two exchange what they know.

The news is usually small: a node joined, a node left, a node looks dead. Researchers also call this style epidemic or infection-style, because news spreads like a cold, one contact at a time.

Push, pull and push-pull

Two nodes can swap news in three ways. A 1987 Xerox PARC paper on epidemic algorithms for replicated databases named all three.

• Push. A node that knows sends the news to its peer.
• Pull. A node asks its peer what is new and copies anything newer.
• Push-pull. Both sides send what they have and take what they lack.

You may read that push is fast at first and pull is slow at first. Our simulation does not show that. With 4,000 nodes, both roughly doubled the informed count every round for the first ten rounds.

The real difference is at the end. A push mostly lands on nodes that already know, while every uninformed node that pulls keeps asking until it finds one that knows. The paper says push-pull behaves essentially like pull there.

Push-pull needed about half the rounds of push at every size. Cassandra, an open-source database, swaps state both ways in a three-message gossip exchange. memberlist, the Go library under the Consul service discovery tool, also runs a full push-pull state sync with one random node. That happens every 30 seconds by default, stretched as the cluster grows: 60 seconds at 40 nodes and 150 at 400.

Gossip reaches every node in a number of rounds that grows with the logarithm of the cluster size. In plain words, doubling the cluster adds only a round or two, not double the time.

Here is why. In round one, one node knows and tells one more. Then two tell two, and four tell four. The informed count roughly doubles each round, until most nodes already know.

The last few nodes take longer, because a random pick usually lands on someone who has already heard. The 1987 paper shows this log-shaped spread for anti-entropy, its name for regular random state swaps.

You can check it yourself. This push-only simulation gives each informed node one random peer per round and counts rounds until every node knows. It averages 100 runs per cluster size.

import random

def rounds_to_spread(n):
    informed = {0}                    # node 0 hears the news first
    rounds = 0
    while len(informed) < n:
        rounds += 1
        for node in list(informed):   # everyone who knows tells one peer
            peer = random.randrange(n)
            if peer != node:
                informed.add(peer)
    return rounds

random.seed(7)                        # same seed, same output
for n in (40, 400, 4000):
    runs = [rounds_to_spread(n) for _ in range(100)]
    print(n, "nodes:", round(sum(runs) / len(runs), 1), "rounds on average")

On Python 3.13.16 it printed 10.1 rounds for 40 nodes, 15.7 for 400 and 21.4 for 4,000. That is 100 times more nodes for about twice the rounds. Other Python versions may print slightly different averages.

Two lines matter. The list(informed) copy means nodes that learn the news this round only start spreading it next round, like a real timer. The peer != node check stops a node gossiping with itself.

The diagram shows the first three rounds for one piece of news. A new node, node 41, has joined the cluster. Follow how each node that hears the news becomes a sender in the next round.

The simplest way is to gossip heartbeat counters. Each node raises its own counter every second, and gossip carries everyone's latest counter around the cluster. A counter that stops rising points to a dead node.

A heartbeat is a small "I am still here" signal. Here it is just a number that only goes up. Node 12 at heartbeat 500 is alive if, a second later, someone hears it at 501.

Each node keeps a membership table: one row per node, with that node's latest heartbeat number. It also stores the local time that number last went up. When two nodes gossip, each keeps the higher counter for every row.

Here is the core of that idea. The merge function runs whenever a gossip message arrives. The suspects function runs once a second and lists nodes whose counters have stalled. The last five lines are a small test.

SUSPECT_AFTER = 5   # seconds without a newer heartbeat

def merge(my_table, their_beats, now):
    for node, beat in their_beats.items():
        row = my_table.get(node)
        if row is None or beat > row["beat"]:
            my_table[node] = {"beat": beat, "seen_at": now}

def suspects(my_table, now):
    return [node for node, row in my_table.items()
            if now - row["seen_at"] > SUSPECT_AFTER]

table = {}
merge(table, {"n12": 500, "n9": 80}, now=100)
merge(table, {"n12": 501, "n9": 80}, now=101)   # n9's counter did not rise
merge(table, {"n12": 499}, now=102)             # old news arrives late
print(table["n12"])
print(suspects(table, now=106))

It prints n12's row as beat 501, seen at 101, then a list holding only n9. The late message with 499 changed nothing. Node n9 is suspected because its counter last rose at second 100.

The key detail is seen_at. It records when this node saw the counter rise, using its own clock. Comparing timestamps written by other machines is risky, because clocks on different machines drift apart.

Apache Cassandra works this way at heart. Its 5.0 docs say that every second each node updates its own heartbeat and gossips with one random peer. It may also contact an unreachable node, and a seed node.

Cassandra versions each node's state with two numbers. The generation is a timestamp that only moves forward, and the version is a logical clock that rises roughly every second. Peers keep whichever state has the higher pair.

One detail surprises people. Cassandra's docs say UP and DOWN are local decisions that are not gossiped. Every node judges every peer for itself, from the heartbeats it hears.

Because the message count grows with the square of the cluster size. With n nodes each sending a heartbeat to all the others, the cluster sends n times (n minus 1) messages per round.

With one round a second, 40 nodes send 1,560 messages per second. At 400 nodes, it is 159,600. With gossip to one peer, each of the 400 nodes sends one message per second, so the cluster sends 400.

The SWIM paper names this exact problem. It says traditional heartbeat protocols either put a load on the network that grows quadratically with group size, or give up speed or accuracy instead.

Here are the four options side by side for a 400-node cluster. The message counts are simple arithmetic, not measurements.

SWIM is a membership protocol from Cornell University, published at the DSN dependability conference in 2002. It splits failure detection from spreading the news. Nodes probe each other directly, and the results travel by gossip.

The name stands for Scalable Weakly-consistent Infection-style process group Membership. A membership protocol keeps a list of live members at every node. Weakly consistent means nodes may briefly disagree about that list.

In each protocol period, a node picks a member and pings it. If an ack, a short reply that says the ping arrived, comes back in time, all is well. The paper's improved version picks targets round-robin from a shuffled list.

If no ack arrives, the node does not give up. It asks a few other members, a small number called k, to ping the target for it. This request is called a ping-req, an indirect probe.

Indirect probes get around a bad link between just two nodes. Say node 4 cannot reach node 9, but node 12 can. Node 12 gets the ack from node 9 and passes it back to node 4.

A direct ping needs two messages to survive, so it fails about 9.75 percent of the time. Each helper path needs four messages. With 3 helpers, node 9 is wrongly suspected only about 0.06 percent of the time.

Those numbers come from our own calculation, checked with a 200,000-trial simulation. They assume losses are independent. Real congestion often drops packets in bursts, so treat them as a best case.

Here is one SWIM round from node 4's point of view. Notice the two question boxes. Only a No at both of them leads to suspicion, and even suspicion is not yet failure.

Suspicion and incarnation numbers

A suspected node is not removed at once. It stays in the membership list, the suspicion is gossiped, and the node gets a timeout to prove it is alive. If the timeout passes with no proof, it is declared failed.

To deny the suspicion, a node uses its incarnation number. This counter starts at 0 when the node joins, and only the node itself can raise it. When node 9 hears it is suspected, it raises the number and gossips that it is alive.

The paper's SWIM sends no separate messages to spread news. Joins, suspicions and failures ride along on the pings and acks it already sends. This is called piggybacking. memberlist piggybacks too, but also sends recent news to 3 random nodes every 200 milliseconds.

The paper says the expected time to first detect a failure does not change with group size. Neither does the expected message load per member. All-to-all heartbeats could not offer both. A central checker could, but only by putting the whole load and the whole judgement on one box.

A phi accrual failure detector gives each peer a suspicion score, called phi, instead of a plain yes or no. The score rises the longer a heartbeat is overdue, compared with that peer's usual timing.

It learns from history. It records the gaps between recent heartbeats from each peer, then asks how unusual the current silence is for that particular peer.

The 2004 paper that introduced it models those gaps with a normal distribution. Phi is minus the base-10 logarithm of the chance that a heartbeat would still arrive this late. In plain words, each extra point means the silence is ten times less likely to be normal.

That gives phi a rough meaning. At phi 1, the chance that a suspicion is a mistake is about 10 percent. At 2 it is about 1 percent, and at 3 about 0.1 percent.

In our check, a peer with steady 1-second gaps, varying by about 0.05 seconds, had phi of about 90 after just 2 silent seconds. A jittery peer, with gaps from 1 to 4 seconds, had phi 0.55 after 3 seconds and 4.6 after 6.

The application picks the threshold. A low one catches real crashes quickly but raises more false alarms. A high one makes fewer mistakes but reacts more slowly.

Cassandra runs a variant of this detector on every node. Its phi_convict_threshold setting defaults to 8, and the docs say most users should never need to change it. Once a node is convicted, Cassandra stops routing reads to it.

Because a failure detector cannot tell a crashed node from a slow node or a broken network path. All it sees is a reply that did not arrive in time.

• Long pauses. A garbage-collection pause, when the runtime stops the program to free memory, or a maxed-out CPU can freeze a node for seconds. It is alive but silent.
• Network trouble. Dropped packets or a full link delay replies, just like the old checker's bad network card.
• A sick prober. A node that is itself overloaded reads replies late, then blames its healthy peers.
• Network partitions. A partition splits the cluster into groups that cannot reach each other. Each side sees the other as dead.

The third cause is the subtle one. In SWIM, a slow prober can mistake its own lateness for other nodes failing. Three HashiCorp engineers studied this in their 2017 Lifeguard paper.

Lifeguard adds three extensions to SWIM. A node that sees signs of its own slowness probes less often and waits longer. Suspicion timeouts shrink as other nodes confirm. And the suspected node is told first, so it can deny quickly.

The paper reports more than a 50x reduction in false positives in its tests. It also shows that false alarms and the detection time for real failures can drop together.

Consul shares membership through a gossip layer called Serf. Its docs say Serf assumes the local node is healthy, and present Lifeguard as the fix when it is not.

Most of these causes trace back to one classic false belief about distributed systems: that the network is reliable. Plan for messages that arrive late, out of order or not at all.

The papers describe mechanisms, and the libraries choose the numbers. We read the source of memberlist v0.7.0 and Cassandra 5.0, as of 19 October 2026. Lifeguard's authors say memberlist underpins Consul.

memberlist: suspicion that shrinks with confirmations

memberlist's default LAN settings probe one node every second and wait 500 milliseconds for an ack. A LAN is the fast network inside one datacenter. A failed probe asks 3 other nodes for indirect pings.

The suspicion timeout depends on cluster size. The minimum is 4 times the base-10 logarithm of the node count, times the 1-second probe interval, and never under 4 seconds. The maximum is 6 times the minimum.

A suspicion starts at the maximum and shrinks toward the minimum as other nodes independently confirm it. With the defaults, 2 confirmations reach the minimum. This is Lifeguard's suspicion idea, built into the timer.

One detail disagrees with itself. The comment beside SuspicionMaxTimeoutMult says it gives a maximum of 120 seconds for 10,000 nodes. The code computes 96 seconds. This is undocumented as of 19 October 2026, so pin your version.

Local health works through an awareness score. At score 0 the probe interval stays 1 second. Each extra point adds another second, up to 8 seconds by default.

Cassandra: phi as silence divided by the average gap

Cassandra 5.0's detector keeps the last 1,000 gaps between heartbeat updates for each peer. It computes phi as the current silence divided by the average gap, times 0.434. From release 5.0.7, it ignores by default any gap longer than 2 seconds, twice the gossip interval, so a peer's average gap never exceeds 2 seconds.

That 0.434 is 1 divided by the natural log of 10. It turns the formula into the exponential form of phi, not the paper's normal one. The source keeps it for backwards compatibility with the default threshold of 8.

So, if updates about a peer arrive once a second on average, phi crosses 8 after about 18.4 seconds of silence. At a 2-second average gap, it takes about 36.8 seconds.

Cassandra also guards against its own pauses. If more than 5 seconds pass between two of its failure checks, it logs a warning and marks no node down for the next 5 seconds. That default comes from cassandra.max_local_pause_in_ms.

Back to the 40-node cache. Each node now runs a small gossip agent with SWIM-style probes, suspicion and local health checks. The client library learns the live node list from any node it talks to.

1. 1

   Join through seeds

   A new node first contacts one of three seed nodes, which are well-known first contacts. The seed shares the current member list, and gossip spreads news of the join.

2. 2

   Probe, gossip and sync

   Each node probes one peer per second and piggybacks recent changes. It also sends them to 3 random nodes every 200 milliseconds. Every 60 seconds at 40 nodes, each node swaps its full table with one other node, as a safety net for missed news. memberlist's 30-second default doubles once a cluster passes 32 nodes.

3. 3

   Suspect, then decide

   A node with no direct or indirect ack becomes suspect. With memberlist defaults at 40 nodes, it has between 6.41 and 38.45 seconds to deny it, depending on confirmations.

4. 4

   Move keys only on failure

   Once a node is declared failed, the client library takes it off the hash ring, the map that assigns keys to nodes. Its keys move to the next nodes on the ring, as consistent hashing intends.

5. 5

   Alert a person

   Every suspect and failed event goes to the on-call dashboard. A node that flips between alive and suspect gets a human look.

Replay the Friday incident against this design. A node with a bad network card may still suspect its peers. But it no longer decides alone: healthy peers deny the suspicion with higher incarnation numbers.

A node frozen for 6 seconds by a long pause usually keeps its keys too. At 40 nodes, even the shortest suspicion window is 6.41 seconds, and it starts only after a probe fails. So the node wakes with time left to deny it.

Explain gossip as the answer to one question: how does every node learn who is alive, without a central point that can fail? Then walk through the steps below.

1. 1

   Name the problem

   Every node needs to know which peers are alive. A central checker is a single point of failure, and its own bad link can fake failures.

2. 2

   Rule out all-to-all heartbeats

   Show the arithmetic: n times (n minus 1) messages per round. At 400 nodes, that is 159,600 a second.

3. 3

   Introduce gossip

   Each node talks to one or a few random peers per round. Load per node stays flat, and news reaches everyone in a logarithmic number of rounds.

4. 4

   Add failure detection

   Describe SWIM: a direct ping, then indirect probes through k peers, then suspicion that the node can deny with its incarnation number.

5. 5

   Handle false alarms

   Mention phi accrual scores, local health checks like Lifeguard, and that a partition looks like death from both sides.

6. 6

   Say what gossip cannot do

   Gossip gives agreement after a delay, not a single truth. Leader election and locks still need a consensus protocol.