SWIM Ping-Request Probes and Why Suspicion Beats Immediate Declaration

A node in a membership protocol has two jobs that pull against each other. It must notice that a peer has stopped, and it must not broadcast a claim that will be hard to retract. A naive detector does the first by timing out a direct probe and the second by being conservative, which makes detection slow. SWIM takes a different route: before it says anything, it spends one extra round trip asking somebody else to try, and it expresses the result as a suspicion that the accused node can cancel rather than as a death certificate.

The probe cycle and the ping-req delegation

Each protocol period, a node picks one peer at random from its membership list and sends a direct ping. If an acknowledgement arrives within the period, the peer is fine and the cycle ends. If it does not, the node does not yet conclude anything. It selects k other members, typically a small constant such as three, and sends each a ping-req naming the unresponsive peer. Those intermediaries send their own direct ping to the target and forward whatever acknowledgement they receive back to the original prober.

The delegation is the mechanism, not a refinement. A single lost packet, a full socket buffer, or a transient routing change between two specific hosts produces a direct-probe failure that is indistinguishable from a crash. The ping-req path is a different path through the network, chosen by a different sender, so an independent success is strong evidence that the target is alive and the original path is at fault. The probe succeeds if any intermediary reports an acknowledgement, and the cost of that evidence is one extra round trip, not a longer timeout. This is why the protocol’s detection time is tied to the protocol period rather than to a tuned multi-second threshold, and why the false-positive arithmetic in heartbeat interval and timeout arithmetic is not the whole story here.

The k intermediaries also carry the load. Because a probe is only delegated after a direct failure, the steady-state message cost is one ping and one acknowledgement per period per node, and the k extra messages appear only when something is already wrong. A full-mesh design that probed every pair would cost quadratic traffic; probing one random peer per period costs a constant number of messages per node per period, and the random selection ensures that over many periods every pair is exercised.

Why random probing still detects every failure

Random peer selection looks like it should weaken completeness. It does not, because the selection is random per period rather than fixed, and because suspicion is disseminated rather than local.

Consider a crashed node. Any prober that selects it will fail the direct ping, fail the delegated pings, and start a suspicion. Each period, the cluster makes n independent selections out of n-1 candidates, so the probability that at least one node picks the crashed one in a given period is close to 1 - e^-1; the time to first suspicion is geometric with a mean of about one period. Once one node suspects, the suspicion spreads through the same gossip channel that carries membership updates, so every node learns within a number of periods logarithmic in n.

The failure mode of random selection is not missed detection but detection variance: the time to first suspicion is a geometric random variable, so occasional failures take several periods. A detector that needs a hard bound on detection time cannot use purely random probing and must either probe a deterministic subset or add an anti-entropy pass over the full list.

Suspicion as a state, not a verdict

When the direct probe and all delegated probes fail, the prober does not mark the target dead. It marks it suspect with a timer, and it gossips the suspicion. The distinction matters for three reasons.

First, a suspicion is revocable without contradiction. A node that is merely slow can refute it, and the refutation is a normal protocol message rather than a special recovery path. A death announcement that later proves wrong requires the system to explain how a dead node came back, and every consumer of the membership list has to handle resurrection.

Second, the timer bounds how long the ambiguity lasts. If the suspicion is not refuted before the timer expires, the suspecting node escalates to dead and gossips that. The timeout is the detector’s accuracy knob: longer means more tolerance for slow nodes, at the cost of slower failover. The escalation is not a new decision but the expiry of an existing one, so it needs no additional messages in the common case.

Third, the state carries the accuser’s identity in some implementations, which lets the accused refute specifically rather than broadcast into the void.

Incarnation numbers and the refutation rule

Every member carries an incarnation number, a monotonically increasing integer that starts at zero when the process starts and is incremented by the process itself. Membership updates are ordered by a pair: the incarnation number first, then the status, with alive beating suspect beating dead at the same incarnation.

The rule that makes refutation work is a comparison. A node that receives a suspicion about itself increments its own incarnation number and gossips an alive message at the new number. Every node that receives it compares the pair and accepts the newer incarnation, which overrides the suspicion. A node that is already dead cannot do this, because it is not running, so the rule distinguishes a slow node from a crashed one using only the node’s own authority over its incarnation.

The subtle part is the ordering of the two fields. If status were compared first, an alive at incarnation 5 would beat a dead at incarnation 9, and a restarted node could reclaim its identity over a correct death announcement about its previous life. Comparing incarnation first means a node’s own increment always wins over any opinion about it formed at a lower incarnation, and a genuinely restarted node must start at an incarnation above anything the cluster has seen, or it will be ignored. A node that restarts with a fresh zero is treated as stale until it increments past the recorded value, which can take as many refutations as the recorded number. Persistent storage of the last incarnation, or seeding it from a value that is guaranteed to increase across restarts, avoids that stall; the choice is a deployment decision rather than a protocol rule, and the protocol only requires the new incarnation to exceed the old.

There is a liveness hazard in the refutation path. A node that is being suspected by many observers at once increments its incarnation once and gossips once; if the gossip is lost, the suspicion stands and it must increment again. Under heavy suspicion the incarnation climbs quickly, and a node that increments faster than its refutations disseminate can win arguments it should lose. Limiting refutation to one increment per received suspicion, with a rate limit, keeps the number meaningful.

The cost of carrying suspicion in the same channel

SWIM piggybacks membership updates on the probe messages rather than sending them separately, which is what keeps the protocol’s message count constant per period. The consequence is that suspicion latency is coupled to probe traffic: a suspicion spreads as fast as probe messages travel, and if the probe rate drops because the cluster is busy, suspicion spreads more slowly.

The other consequence is that a suspicion can arrive at a node that has more recent information than the sender. The merge rule handles this without coordination, because the incarnation and status comparison is a total order on updates and is idempotent: applying the same update twice changes nothing, and applying a stale one changes nothing. That property is what makes the gossip channel safe without acknowledgements, and it is the same property that gossip propagation of suspicion depends on when the suspicion set grows beyond what fits in a probe message.

What the protocol does not promise

SWIM gives weak consistency: two nodes can hold different views of membership at the same instant, and no node can tell whether its view is current. It detects crashes probabilistically, with no hard upper bound on detection time for a specific node. It does not detect a node that is alive but partitioned from the prober while reachable from the intermediaries, because the intermediaries will report success and the prober will believe them.

That last case is the important one. A successful ping-req proves reachability along some path, not global health, and a system that needs to distinguish “this node cannot serve me” from “this node is gone” needs a different mechanism. The per-observer view and the way to combine views are the subject of asymmetric partitions and per-observer diagnosis. SWIM answers a narrower question well: is there any path from the group to this node, and if nobody can find one for long enough, stop counting it.