How to Detect Failed Nodes in Python With Heartbeat Timeouts, the Phi Accrual Detector, and SWIM-Style Probing

Every cluster has to answer one question over and over: is that node dead, or only slow? Nobody can answer it with certainty. A heartbeat that has not arrived might be lost, might be held up by a garbage collection pause, or might never have been sent because the sender crashed, and from the receiving side those three cases look exactly alike. A failure detector is the code that turns that uncertainty into a decision your system can act on, and every design is a bet on how you would rather be wrong.

In this tutorial you will build three detectors in plain Python, run them against a simulated network that you can make calm or rough, and measure the two things that matter: how often each one accuses a healthy node (a false alarm) and how long each takes to notice a node that really crashed. You will start with the fixed timeout that Kubernetes uses for its nodes, move on to the φ (phi) accrual detector that Apache Pekko and Apache Cassandra ship, and finish with the probing scheme from the SWIM protocol, which stops a single observer from being the only judge. You need no cluster, no Docker and no cloud account, because everything runs in one process on a fake clock.

One honest warning before you start. The delays, losses and stalls in this lab come from a random generator with fixed seeds, so every number below is a measurement of a model, not of a real network. What does carry over to real systems is how each detector behaves when its assumptions stop being true, and that is where most production surprises hide.

What you will build, and the words you need first

By the end you will have:

• a seeded model of a heartbeat link with a calm setting and a busy setting;
• a scoring harness that reports false alarms per hour and detection time;
• three detectors: a fixed timeout, a φ accrual detector that assumes a normal distribution (the kind Apache Pekko uses), and an exponential version (the kind Apache Cassandra uses);
• a SWIM-style probe that asks other members for a second opinion, plus a model of who probes whom;
• 25 tests, and a script that plants nine bugs to prove the tests notice them.

This covers the failure detector half of SWIM only. The other half, which spreads news about who is alive, and the suspicion timer are explained in words and sources but not built.

A few terms, defined before they are used. A heartbeat is a small message that a node sends at a steady interval to say “I am still here”. The monitor is the node that receives them. Silence is the time since the monitor last heard a heartbeat. A detector suspects a node when the silence passes a limit, and I call that limit the horizon (my own word, so that one number can describe every detector in this tutorial). A suspicion is a judgement, not a fact. A false alarm is a suspicion of a node that was alive, and detection time is how long a node that really crashed stays unsuspected. Making one smaller usually makes the other bigger, and the rest of the tutorial is about that trade.

Prerequisites

• Python 3.10 or newer. Every command below ran on Python 3.13.14 on Windows 11. pytest 9.1.1 declares Requires-Python >=3.10, and the lab code itself uses only the standard library.
• A bash shell. On Windows I used Git Bash; the activation line differs, as noted in Step 1. Linux and macOS need nothing extra.
• One package: pytest 9.1.1, for the tests in Step 6.
• Background: you can read a Python class and a list. You do not need statistics. The two bits of probability we use are explained where they appear.

Step 1: Create the project and a network you can break on purpose

Start with an empty folder and a virtual environment (a private set of installed packages for this project):

$ mkdir fd_lab
$ cd fd_lab
$ python -m venv .venv
$ source .venv/bin/activate
$ python -m pip install pytest==9.1.1

On Windows in Git Bash, the activation line is source .venv/Scripts/activate. All the files below go in this one folder. The first line of every code block is a comment with the file name, and a block whose first line says “(continued)” belongs at the end of the file that was started earlier.

Failure detection depends on time, and real time makes bad test material: you would wait through real seconds, and every run would give different numbers. So the lab never reads a clock. It builds a trace, which is the list of moments at which each heartbeat reached the monitor, from a random generator with a fixed seed. Create netmodel.py:

# netmodel.py
"""A seeded model of the heartbeats that one node sends to the node watching it.

A heartbeat leaves every `interval` seconds. Each one is lost with probability `loss`;
the rest are delayed by a log-normal amount (most delays sit near the median, a few are much longer).
A stall (a garbage collection pause, a congested link) holds back everything sent while it lasts
and releases it all when it ends.
"""
import bisect
import math
import random
from dataclasses import dataclass


@dataclass(frozen=True)
class Regime:
    name: str
    median_delay: float  # seconds
    sigma: float         # spread of the log-normal delay
    loss: float          # chance that one heartbeat never arrives
    stall_every: float   # mean seconds between stalls, 0 means no stalls
    stall_low: float     # shortest stall, seconds
    stall_high: float    # longest stall, seconds


CALM = Regime("calm", 0.020, 0.30, 0.001, 0.0, 0.0, 0.0)
BUSY = Regime("busy", 0.150, 0.90, 0.010, 900.0, 1.5, 3.0)


@dataclass(frozen=True)
class Trace:
    sent: list       # send time of each heartbeat that arrived, in arrival order
    arrived: list    # arrival time of the same heartbeats
    duration: float  # seconds covered


def _stalls(rng, regime, start, length):
    spans = []
    if regime.stall_every <= 0:
        return spans
    t = rng.expovariate(1.0 / regime.stall_every)
    while t < length:
        span = rng.uniform(regime.stall_low, regime.stall_high)
        spans.append((start + t, start + t + span))
        t += span + rng.expovariate(1.0 / regime.stall_every)
    return spans


def make_trace(segments, interval=1.0, seed=1):
    """segments is a list of (Regime, seconds). Returns the heartbeats that arrive, in arrival order."""
    rng = random.Random(seed)
    edges, stalls, begin = [], [], 0.0
    for regime, length in segments:
        edges.append((begin, regime))
        stalls.extend(_stalls(rng, regime, begin, length))
        begin += length
    starts = [b for b, _ in edges]
    beats = []
    for seq in range(1, int(begin / interval) + 1):
        sent = seq * interval
        regime = edges[bisect.bisect_right(starts, sent) - 1][1]
        if rng.random() < regime.loss:
            continue
        release = max([end for first, end in stalls if first <= sent < end], default=sent)
        delay = regime.median_delay * math.exp(rng.gauss(0.0, regime.sigma))
        beats.append((release + delay, seq, sent))
    beats.sort()
    sent_out, arrived_out, newest = [], [], 0
    for arrival, seq, sent in beats:
        if seq > newest:  # a late copy of an older heartbeat tells the monitor nothing new
            newest = seq
            sent_out.append(sent)
            arrived_out.append(arrival)
    return Trace(sent_out, arrived_out, begin)

Read it from the top. A Regime is a bundle of numbers that describes one kind of network: the median delay, how spread out the delays are (sigma), the chance that a heartbeat is lost, and how often the link stalls. A stall holds back everything sent while it lasts and delivers it all when it ends, which is what a garbage collection pause or a congested link looks like from outside: a long silence, then a burst. I made two regimes. CALM is a quiet local network (20 ms median delay, one heartbeat lost in a thousand, no stalls). BUSY has a 150 ms median delay with a long tail of slow arrivals, one heartbeat lost in a hundred, and a stall of 1.5 to 3 seconds about every 15 minutes.

Delays use a log-normal distribution, a common modelling choice because it cannot go below zero and has a long tail of rare slow arrivals. make_trace sends one heartbeat per second, numbered 1, 2, 3 and so on. It drops lost ones, holds back the ones sent during a stall, adds a random delay, and sorts by arrival time. Finally it throws away any heartbeat that arrives after a newer one, because it tells the monitor nothing new. Real protocols do this with sequence numbers; the paper behind the φ detector, which you will meet in Step 3, says the monitored process “adds a sequence number to each heartbeat message”.

Now check what the two networks look like. step01_trace.py builds an hour of each and prints the longest silences:

# step01_trace.py
from netmodel import BUSY, CALM, make_trace

for regime in (CALM, BUSY):
    trace = make_trace([(regime, 3600.0)], seed=1)
    gaps = sorted(later - earlier for earlier, later in zip(trace.arrived, trace.arrived[1:]))
    delays = sorted(arrival - sent for arrival, sent in zip(trace.arrived, trace.sent))
    print(f"{regime.name}: {len(trace.arrived)} of 3600 heartbeats counted, median delay {delays[len(delays) // 2] * 1000:.0f} ms, "
          f"longest silence {gaps[-1]:.2f} s, 99.9th percentile of silences {gaps[int(0.999 * len(gaps))]:.2f} s")

Run python step01_trace.py:

calm: 3597 of 3600 heartbeats counted, median delay 20 ms, longest silence 2.01 s, 99.9th percentile of silences 1.04 s
busy: 3513 of 3600 heartbeats counted, median delay 149 ms, longest silence 3.62 s, 99.9th percentile of silences 2.74 s

Two details are worth understanding before you move on. First, a lost heartbeat shows up as a silence of about two intervals, which is why the calm network’s longest silence is 2.01 s even though its delays are tiny. Second, on the busy network 99.9 percent of silences are under 2.74 s but the longest is 3.62 s, and the counted total (3,513 of 3,600) is lower because some heartbeats were lost and others were overtaken by newer ones. Those two numbers, how long a healthy node is normally silent and how long it is sometimes silent, are what every detector in this tutorial is trying to guess.

Step 2: The fixed timeout, and what it costs

Build the scorer first

Before writing any detector, write the thing that grades it, so every detector is judged by the same rule. Every detector in this tutorial has two methods: heartbeat(now), which tells it a heartbeat just arrived, and horizon(), which answers “how many seconds of silence from now on would make you suspect the node?”. Create evaluate.py:

# evaluate.py
"""Replay a trace through a detector and score it on the two things that matter:
false alarms while the node is alive, and how long a real crash takes to notice."""
import bisect
import random


def horizons_after_each_arrival(detector, trace):
    """Feed the arrivals in order and record how long a silence the detector tolerates after each one."""
    horizons = []
    for arrival in trace.arrived:
        detector.heartbeat(arrival)
        horizons.append(detector.horizon())
    return horizons


def alarm_times(make_detector, trace):
    """Moments (the arrival that began the long silence) after which a live node was wrongly suspected."""
    horizons = horizons_after_each_arrival(make_detector(), trace)
    arrived = trace.arrived
    return [arrived[i] for i in range(len(arrived) - 1) if arrived[i + 1] - arrived[i] > horizons[i]]


def score(make_detector, trace, start=120.0, end=None, crashes=400, seed=7):
    """False alarms per hour and detection time, both measured between start and end (seconds into the trace)."""
    end = trace.duration - 60.0 if end is None else end
    horizons = horizons_after_each_arrival(make_detector(), trace)
    arrived, sent = trace.arrived, trace.sent
    alarms = sum(
        1 for i in range(len(arrived) - 1)
        if start <= arrived[i] < end and arrived[i + 1] - arrived[i] > horizons[i]
    )
    rng = random.Random(seed)
    waits = []
    for _ in range(crashes):
        crash = rng.uniform(start, end)
        i = bisect.bisect_right(sent, crash) - 1  # the last heartbeat that left before the crash
        waits.append(max(0.0, arrived[i] + horizons[i] - crash))
    waits.sort()
    hours = (end - start) / 3600.0
    return {
        "alarms": alarms,
        "per_hour": alarms / hours,
        "mean": sum(waits) / len(waits),
        "p99": waits[int(0.99 * len(waits))],
    }

The scorer replays a trace and asks the detector for its horizon after every arrival. A false alarm is a gap between two consecutive arrivals that was longer than the horizon in force: the detector would have suspected a node that was in fact about to send its next heartbeat. The comparison is strictly “longer than”, and a test in Step 6 pins that down. Detection time is measured by pretending the node crashes at a random moment. Heartbeats that had already left still arrive (they were in flight), and the detector notices when the silence after the last of them reaches its horizon: arrived[i] + horizons[i] - crash. The first 120 seconds are skipped (start=120.0) so that detectors that learn have some history before they are judged.

One simplification to remember: the scorer assumes the monitor checks continuously. A real monitor checks on a timer, which adds up to one check period to every detection time. The Kubernetes node controller, for example, “checks the state of each node every 5 seconds” by default, according to the Kubernetes node documentation.

The simplest detector

The most common failure detector is a timeout: if nothing has arrived for T seconds, the node is suspected. Start detectors.py with it. The imports at the top are for the detectors you will add in Step 3:

# detectors.py
"""Three ways to decide that a silent node has failed. Each one answers the same question through horizon():
how many seconds of silence after the latest heartbeat make the node suspected?"""
import math
from collections import deque
from statistics import NormalDist

_NORMAL = NormalDist()


class FixedTimeout:
    """Suspect the node once `timeout` seconds pass without a heartbeat."""

    def __init__(self, timeout):
        self.timeout = timeout

    def heartbeat(self, now):
        pass

    def horizon(self):
        return self.timeout

The horizon never changes, whatever the network has been doing. Now measure it. step02_fixed.py tries four timeouts on four hours of each network:

# step02_fixed.py
from detectors import FixedTimeout
from evaluate import score
from netmodel import BUSY, CALM, make_trace

HOURS = 4
print(f"{'regime':7} {'timeout':>8} {'false alarms/hour':>18} {'mean detection':>15} {'99th percentile':>16}")
for regime in (CALM, BUSY):
    trace = make_trace([(regime, HOURS * 3600.0)], seed=1)
    for timeout in (1.5, 2.5, 3.5, 5.5):
        result = score(lambda: FixedTimeout(timeout), trace)
        print(f"{regime.name:7} {timeout:7.1f}s {result['per_hour']:18.1f} {result['mean']:14.2f}s {result['p99']:15.2f}s")

Run python step02_fixed.py:

regime   timeout  false alarms/hour  mean detection  99th percentile
calm        1.5s                4.6           1.03s            1.51s
calm        2.5s                0.0           2.03s            2.51s
calm        3.5s                0.0           3.03s            3.51s
calm        5.5s                0.0           5.03s            5.51s
busy        1.5s              224.1           1.20s            2.01s
busy        2.5s                5.1           2.20s            3.01s
busy        3.5s                0.0           3.20s            4.01s
busy        5.5s                0.0           5.20s            6.01s

Reading the table

On the calm network a 1.5 s timeout makes 4.6 false alarms an hour, because every lost heartbeat leaves a gap of about 2 s. A 2.5 s timeout makes none and notices a crash after 2.03 s on average. That average is the timeout minus about half an interval: on average the last heartbeat arrived half an interval before the crash, so the timeout has already run for that long.

The busy network is where the trouble starts. The same 1.5 s timeout makes 224.1 false alarms an hour, and even 2.5 s makes 5.1. Only 3.5 s and above is quiet in this run. So the best single timeout for both networks is 3.5 s, which leaves the calm network waiting 3.03 s instead of 2.03 s to notice a real crash. A fixed number forces you to choose which network to be wrong in. Kubernetes makes that choice with fixed numbers. The kubelet renews a Lease object every 10 seconds, the lease duration defaults to 40 seconds, and the controller manager’s --node-monitor-grace-period defaults to 50 seconds (see the kubelet configuration reference and the kube-controller-manager reference). The flag’s own description calls it the time the controller will “allow running Node to be unresponsive before marking it unhealthy”, so a node can stay silent for most of a minute before anything happens.

Step 3: The φ accrual detector, a suspicion level instead of a yes or no

The idea in one paragraph

In 2004 Hayashibara, Défago, Yared and Katayama proposed that a detector should not answer yes or no. In their words, “accrual failure detectors output a suspicion level on a continuous scale”, and the application picks the threshold it can live with. Their implementation, the φ detector, remembers how far apart the last heartbeats arrived, assumes those gaps follow a normal (bell curve) distribution, and asks: given that curve, how unlikely is it that a healthy node is still silent this long? Call that probability p_later. Then the suspicion level is

phi(now) = -log10(p_later(now - last_arrival))

The scale is logarithmic, so every step of 1 means ten times less likely to be a coincidence. The paper’s own reading: if you suspect at φ = 1, about 10 percent of the time a late heartbeat will contradict you; at φ = 2 it is about 1 percent, at φ = 3 about 0.1 percent, and so on.

A worked example. Say the last heartbeats arrived 1.0 s apart on average with a spread (standard deviation) of 0.1 s. A silence of 1.2 s is two spreads past the average, and a healthy node is that late only about 2.3 percent of the time, so phi = -log10(0.023) = 1.64. A silence of 1.56 s is 5.6 spreads out, which happens about once in a hundred million heartbeats, so φ = 8. That is the point where a threshold of 8 fires. The important part is that the same silence means something different on a different network, because the average and the spread come from that network’s own recent history.

The code

Add the history window and the detector to detectors.py. The window keeps the most recent intervals and running sums, so the mean and spread cost the same however many intervals it holds:

# detectors.py (continued)
class _Window:
    """The most recent heartbeat intervals, with running sums so that mean and spread cost O(1)."""

    def __init__(self, size, first_interval, max_interval):
        self.size = size
        self.max_interval = max_interval
        self.values = deque()
        self.total = 0.0
        self.total_sq = 0.0
        self.last = None
        # Pekko seeds the history with two made-up intervals so that phi works before any real data exists.
        for seed_value in (0.75 * first_interval, 1.25 * first_interval):
            self._add(seed_value)

    def _add(self, value):
        self.values.append(value)
        self.total += value
        self.total_sq += value * value
        if len(self.values) > self.size:
            old = self.values.popleft()
            self.total -= old
            self.total_sq -= old * old

    def heartbeat(self, now):
        if self.last is not None:
            interval = now - self.last
            # Cassandra never records an interval longer than its cap, so an outage cannot teach the detector
            # that long silences are normal.
            if self.max_interval is None or interval <= self.max_interval:
                self._add(interval)
        self.last = now

    def mean_std(self):
        n = len(self.values)
        mean = self.total / n
        return mean, math.sqrt(max(0.0, self.total_sq / n - mean * mean))


class PhiAccrual:
    """Phi accrual with a normal distribution of intervals (Hayashibara et al. 2004, and Apache Pekko)."""

    def __init__(self, threshold=8.0, window=1000, min_std=0.1, pause=0.0, first_interval=1.0, max_interval=None):
        self.threshold = threshold
        self.min_std = min_std
        self.pause = pause
        self.window = _Window(window, first_interval, max_interval)
        self._z = -_NORMAL.inv_cdf(10.0 ** -threshold)

    def heartbeat(self, now):
        self.window.heartbeat(now)

    def mean_std(self):
        mean, std = self.window.mean_std()
        return mean, max(std, self.min_std)

    def phi(self, silence):
        mean, std = self.mean_std()
        y = (silence - (mean + self.pause)) / std
        p_later = 0.5 * math.erfc(y / math.sqrt(2.0))  # chance that a heartbeat arrives later than this
        return math.inf if p_later <= 0.0 else -math.log10(p_later)

    def horizon(self):
        mean, std = self.mean_std()
        return mean + self.pause + std * self._z

Four details matter here. The first three come from Apache Pekko’s implementation (PhiAccrualFailureDetector.scala), and its reference.conf explains them well. The fourth is my own shortcut:

• Seeding. A new detector has no history, so Pekko starts it with two made-up intervals, the expected interval minus a quarter and plus a quarter. _Window does the same.
• min_std, the floor on the spread. Pekko’s configuration comment says: “Too low standard deviation might result in too much sensitivity for sudden, but normal, deviations in heartbeat inter arrival times.” Its default is 100 ms.
• pause, the allowance. Pekko calls it acceptable-heartbeat-pause (default 3 s) and describes it as the number of potentially lost or delayed heartbeats that will be accepted before considering it to be an anomaly, so that the detector can “survive sudden, occasional, pauses in heartbeat arrivals, due to for example garbage collect or network drop”. It simply shifts the average up.
• The horizon in closed form. Instead of searching for the silence at which φ reaches the threshold, horizon() solves for it: the average, plus the allowance, plus the spread times z, where z is the point on the bell curve whose upper tail is 10 to the power of minus the threshold. statistics.NormalDist().inv_cdf computes it. For a threshold of 8, z is about 5.6.

One difference from Pekko to know about: phi() here uses the exact normal curve through math.erfc. Pekko’s source uses a logistic curve as a stand-in for the normal one and notes that its error is 0.00014 at plus or minus 3.16. Near the middle the two agree closely, but far out in the tail they drift apart, and a test in Step 6 measures how far.

Look at φ

step03_phi_scale.py trains a detector on 50 minutes of each network and prints φ for several silences:

# step03_phi_scale.py
from detectors import PhiAccrual
from netmodel import BUSY, CALM, Regime, make_trace

SILENCES = (1.0, 1.2, 1.5, 2.0, 3.0)


def trained(regime, **options):
    detector = PhiAccrual(**options)
    for arrival in make_trace([(regime, 3000.0)], seed=2).arrived:
        detector.heartbeat(arrival)
    return detector


print("Same silence, different history (threshold 8, floor 0.1 s, no pause allowance)")
for regime in (CALM, BUSY):
    detector = trained(regime)
    mean, std = detector.mean_std()
    print(f"{regime.name}: mean interval {mean:.3f} s, spread {std:.3f} s")
    print("  silence (s)  " + "".join(f"{s:8.1f}" for s in SILENCES))
    print("  phi          " + "".join(f"{detector.phi(s):8.2f}" for s in SILENCES))
    print(f"  suspected after {detector.horizon():.2f} s of silence")

print()
print("What the spread floor does when the history is perfectly regular (no lost heartbeats)")
CLEAN = Regime("clean", 0.020, 0.30, 0.0, 0.0, 0.0, 0.0)
for floor in (0.001, 0.01, 0.1):
    detector = trained(CLEAN, min_std=floor)
    print(f"  floor {floor:5.3f} s: spread used {detector.mean_std()[1]:.3f} s, phi after 1.2 s of silence = {detector.phi(1.2):9.2f}, suspected after {detector.horizon():.2f} s")

Run python step03_phi_scale.py:

Same silence, different history (threshold 8, floor 0.1 s, no pause allowance)
calm: mean interval 1.003 s, spread 0.100 s
  silence (s)       1.0     1.2     1.5     2.0     3.0
  phi              0.29    1.61    6.48   22.99   88.30
  suspected after 1.56 s of silence
busy: mean interval 1.028 s, spread 0.347 s
  silence (s)       1.0     1.2     1.5     2.0     3.0
  phi              0.27    0.51    1.06    2.60    8.19
  suspected after 2.97 s of silence

What the spread floor does when the history is perfectly regular (no lost heartbeats)
  floor 0.001 s: spread used 0.009 s, phi after 1.2 s of silence =    109.63, suspected after 1.05 s
  floor 0.010 s: spread used 0.010 s, phi after 1.2 s of silence =     88.57, suspected after 1.06 s
  floor 0.100 s: spread used 0.100 s, phi after 1.2 s of silence =      1.64, suspected after 1.56 s

Look at the 1.5 s column. After a calm history a silence of 1.5 s scores φ = 6.48, nearly at the threshold of 8, and the node is suspected after 1.56 s. After a busy history the same 1.5 s scores only 1.06, and the node is not suspected until 2.97 s. The detector worked out for itself that silences are normal on the busy link. Note that the calm spread reads 0.100 s: that is the floor, not the measurement.

The second table shows why the floor exists. I fed the detector a perfectly regular history with no lost heartbeats, where the real spread is only 0.009 s. With a 0.001 s floor, a heartbeat that is merely 0.2 s late scores φ = 109.63 and the node is suspected after 1.05 s, which is 50 ms of lateness. With the 0.1 s floor, that same 1.2 s silence scores 1.64. A detector that learns from very regular traffic would otherwise treat any ripple as a death.

Step 4: Compare the detectors, and learn why “threshold 8” means two different things

Add Cassandra’s version to the end of detectors.py. Cassandra’s FailureDetector.java computes phi = t / mean(), the silence divided by the mean interval, and compares PHI_FACTOR * phi with its phi_convict_threshold, where PHI_FACTOR is 1.0 / Math.log(10.0). That is what the -log10 formula gives when the gaps follow an exponential distribution, where only the mean matters (my derivation; a comment in the source points to CASSANDRA-2597 for the math):

# detectors.py (continued)
class ExponentialPhi:
    """Cassandra's variant: only the mean interval matters, and phi = silence / mean / ln(10)."""

    def __init__(self, threshold=8.0, window=1000, first_interval=1.0, max_interval=None):
        self.threshold = threshold
        self.window = _Window(window, first_interval, max_interval)

    def heartbeat(self, now):
        self.window.heartbeat(now)

    def phi(self, silence):
        mean, _ = self.window.mean_std()
        return silence / mean / math.log(10.0)

    def horizon(self):
        mean, _ = self.window.mean_std()
        return self.threshold * math.log(10.0) * mean

The method also takes a max_interval, which I will come back to in the mistakes section. Now line everything up. step04_compare.py runs seven detector settings on four hours of each network:

# step04_compare.py
from detectors import ExponentialPhi, FixedTimeout, PhiAccrual
from evaluate import score
from netmodel import BUSY, CALM, make_trace

HOURS = 4
CASES = [
    ("fixed 2.5 s", lambda: FixedTimeout(2.5)),
    ("fixed 5.5 s", lambda: FixedTimeout(5.5)),
    ("phi 8, no allowance", lambda: PhiAccrual(threshold=8.0)),
    ("phi 8, 1 s allowance", lambda: PhiAccrual(threshold=8.0, pause=1.0)),
    ("phi 8, 3 s allowance", lambda: PhiAccrual(threshold=8.0, pause=3.0)),
    ("exponential phi 8", lambda: ExponentialPhi(threshold=8.0)),
    ("exponential phi 3", lambda: ExponentialPhi(threshold=3.0)),
]
print(f"{'regime':6} {'detector':21} {'tolerates':>10} {'false alarms/h':>15} {'mean detection':>15} {'99th percentile':>16}")
for regime in (CALM, BUSY):
    trace = make_trace([(regime, HOURS * 3600.0)], seed=1)
    for label, factory in CASES:
        detector = factory()
        for arrival in trace.arrived:
            detector.heartbeat(arrival)
        tolerated = detector.horizon()  # the silence it would accept after the last heartbeat of the trace
        result = score(factory, trace)
        print(f"{regime.name:6} {label:21} {tolerated:9.2f}s {result['per_hour']:15.1f} {result['mean']:14.2f}s {result['p99']:15.2f}s")

Run python step04_compare.py. The “tolerates” column is the silence the detector would accept after its last heartbeat:

regime detector               tolerates  false alarms/h  mean detection  99th percentile
calm   fixed 2.5 s                2.50s             0.0           2.03s            2.51s
calm   fixed 5.5 s                5.50s             0.0           5.03s            5.51s
calm   phi 8, no allowance        1.56s             4.6           1.09s            1.57s
calm   phi 8, 1 s allowance       2.56s             0.0           2.09s            2.57s
calm   phi 8, 3 s allowance       4.56s             0.0           4.09s            4.57s
calm   exponential phi 8         18.42s             0.0          17.98s           18.46s
calm   exponential phi 3          6.91s             0.0           6.45s            6.93s
busy   fixed 2.5 s                2.50s             5.1           2.20s            3.01s
busy   fixed 5.5 s                5.50s             0.0           5.20s            6.01s
busy   phi 8, no allowance        2.72s             2.5           2.49s            3.28s
busy   phi 8, 1 s allowance       3.72s             0.0           3.49s            4.28s
busy   phi 8, 3 s allowance       5.72s             0.0           5.49s            6.28s
busy   exponential phi 8         18.88s             0.0          18.55s           19.39s
busy   exponential phi 3          7.08s             0.0           6.77s            7.59s

What the table says

The allowance does the heavy lifting. With no allowance, φ = 8 on the calm network tolerates 1.56 s and makes 4.6 false alarms an hour, exactly what the fixed 1.5 s timeout did, because the culprit is the same: lost heartbeats. Add a one-second allowance and the calm network goes to zero false alarms with a 2.09 s detection time, about the same as a fixed 2.5 s timeout (2.03 s). Since this detector adjusts to what it sees, the same setting tolerates 3.72 s on the busy network and also makes zero false alarms there, at a 3.49 s detection time.

The honest comparison. The best single fixed timeout with zero false alarms on both networks is 3.5 s, with mean detection times of 3.03 s (calm) and 3.20 s (busy). The φ detector with a one-second allowance also had zero false alarms on both, with 2.09 s and 3.49 s. So in this lab it is about 0.9 s faster on the calm network and 0.3 s slower on the busy one. That is a real gain, but a modest one. Its main value is that you do not have to retune the setting per environment.

φ = 8 is a promise made by a curve, not by the network. Under the normal curve a threshold of 8 means roughly one mistake in a hundred million heartbeats. What I measured with no allowance was 4.6 false alarms an hour on the calm network, about one in 780 heartbeats, and 2.5 an hour on the busy one, about one in 1,400. The curve cannot see lost heartbeats or rare long delays, so its promise does not hold. Measure the mistake rate in your own environment instead of trusting the number.

The same “8” means something very different elsewhere. The last two rows for each network use the exponential version. With a threshold of 8, the horizon is 8 × ln(10) ≈ 18.4 mean intervals (my arithmetic from the code above), and the table shows 18.42 s on the calm network and 18.88 s on the busy one. Pekko’s default threshold is also 8.0, but there it marks a point roughly five spreads beyond the average plus the allowance. In this lab’s version of that detector it is 1.56 s on the calm network, or 4.56 s with Pekko’s default allowance of 3 s. Cassandra’s cassandra.yaml says of its own setting: “phi value that must be reached for a host to be marked down. most users should never need to adjust this.” When you move between systems, or read an operations guide written for another one, check which distribution is assumed before you copy a threshold.

Step 5: Watch the detectors adapt when the network changes

An adaptive detector is only worth having if it follows changes. step05_switch.py builds a three-hour trace, one hour calm, one hour busy, one hour calm again, and scores four detectors on each hour. It also prints how the detectors behave in the first ten-minute slices after each switch, using the alarm_times helper:

# step05_switch.py
from detectors import FixedTimeout, PhiAccrual
from evaluate import alarm_times, score
from netmodel import BUSY, CALM, make_trace

HOUR = 3600.0
trace = make_trace([(CALM, HOUR), (BUSY, HOUR), (CALM, HOUR)], seed=3)
CASES = [
    ("fixed 2.5 s", lambda: FixedTimeout(2.5)),
    ("fixed 5.5 s", lambda: FixedTimeout(5.5)),
    ("phi 8, 1 s allowance", lambda: PhiAccrual(threshold=8.0, pause=1.0, window=1000)),
    ("phi 8, window of 100", lambda: PhiAccrual(threshold=8.0, pause=1.0, window=100)),
]
PHASES = [("calm", 120.0, HOUR), ("busy", HOUR, 2 * HOUR), ("calm again", 2 * HOUR, 3 * HOUR - 60.0)]

print(f"{'detector':21} {'phase':11} {'false alarms':>13} {'mean detection':>15}")
for label, factory in CASES:
    for phase, start, end in PHASES:
        result = score(factory, trace, start=start, end=end)
        print(f"{label:21} {phase:11} {result['alarms']:13d} {result['mean']:14.2f}s")

print()
print("False alarms in each 10 minutes after the network turns busy (at the 1 hour mark)")
for label, factory in CASES:
    times = alarm_times(factory, trace)
    counts = [sum(1 for t in times if HOUR + 600 * b <= t < HOUR + 600 * (b + 1)) for b in range(6)]
    print(f"{label:21} " + " ".join(f"{n:3d}" for n in counts))

print()
print("Mean detection time in each 10 minutes after the network calms down again (at the 2 hour mark)")
for label, factory in CASES:
    means = [score(factory, trace, start=2 * HOUR + 600 * b, end=2 * HOUR + 600 * (b + 1), crashes=300)["mean"] for b in range(6)]
    print(f"{label:21} " + " ".join(f"{m:5.2f}" for m in means))

Run python step05_switch.py:

detector              phase        false alarms  mean detection
fixed 2.5 s           calm                    0           2.03s
fixed 2.5 s           busy                    6           2.22s
fixed 2.5 s           calm again              0           2.04s
fixed 5.5 s           calm                    0           5.03s
fixed 5.5 s           busy                    0           5.22s
fixed 5.5 s           calm again              0           5.04s
phi 8, 1 s allowance  calm                    0           2.09s
phi 8, 1 s allowance  busy                    1           3.28s
phi 8, 1 s allowance  calm again              0           2.31s
phi 8, window of 100  calm                    0           2.09s
phi 8, window of 100  busy                    0           3.44s
phi 8, window of 100  calm again              0           2.13s

False alarms in each 10 minutes after the network turns busy (at the 1 hour mark)
fixed 2.5 s             1   2   1   1   0   1
fixed 5.5 s             0   0   0   0   0   0
phi 8, 1 s allowance    1   0   0   0   0   0
phi 8, window of 100    0   0   0   0   0   0

Mean detection time in each 10 minutes after the network calms down again (at the 2 hour mark)
fixed 2.5 s            2.00  2.00  2.00  2.00  2.00  2.00
fixed 5.5 s            5.00  5.00  5.00  5.00  5.00  5.00
phi 8, 1 s allowance   2.96  2.23  2.06  2.07  2.06  2.06
phi 8, window of 100   2.19  2.06  2.06  2.07  2.06  2.06

Reading the three tables

In the busy hour, the fixed 2.5 s timeout raised 6 false alarms, the φ detector with a window of 1,000 intervals raised 1, and the one with a window of 100 raised none. The fixed 5.5 s timeout raised none too, at the price of a 5 s detection time on every network. The ten-minute table shows the φ detector’s only alarm came in the first ten minutes, before its history had caught up. Counts this small come from one trace with one seed, so read them as “no sign of trouble”, not as a ranking.

The last table shows the cost of adapting. When the calm network returns, the detector with the 1,000-interval window needs about twenty minutes to forget the busy hour: its mean detection time is 2.96 s in the first ten minutes, 2.23 s in the next, and settles at about 2.06 s. The window of 100 recovers in the first slice (2.19 s) but, with fewer samples, its average and spread are noisier. At one heartbeat per second, 1,000 intervals is about 17 minutes of memory. Pekko’s max-sample-size defaults to 1,000 and Cassandra’s SAMPLE_SIZE is fixed at 1,000 in its source, so you inherit about that much memory.

Step 6: Lock the behaviour in with tests, then break the code on purpose

Detectors fail quietly: a wrong formula still returns numbers. So put the facts you have learned into tests. Create test_fd.py:

# test_fd.py
import math
import random

import pytest

from detectors import ExponentialPhi, FixedTimeout, PhiAccrual
from evaluate import score
from netmodel import BUSY, Trace, make_trace
from swim import expected_false_positive, probe, wait_for_first_probe


def regular(detector, count=50, gap=1.0):
    """Feed a detector a perfectly regular heartbeat."""
    now = 100.0
    detector.heartbeat(now)
    for _ in range(count):
        now += gap
        detector.heartbeat(now)
    return detector


def pekko_phi(silence, mean, std):
    """Apache Pekko's phi: a logistic curve standing in for the normal distribution."""
    y = (silence - mean) / std
    e = math.exp(-y * (1.5976 + 0.070566 * y * y))
    return -math.log10(e / (1.0 + e)) if silence > mean else -math.log10(1.0 - 1.0 / (1.0 + e))


# --- the detectors -------------------------------------------------------------------------------

def test_fixed_timeout_horizon_is_the_timeout():
    assert FixedTimeout(2.5).horizon() == 2.5


def test_phi_is_log10_of_two_when_the_silence_equals_the_mean():
    detector = regular(PhiAccrual())
    mean, _ = detector.mean_std()
    assert mean == pytest.approx(1.0)
    assert detector.phi(mean) == pytest.approx(math.log10(2.0))


def test_phi_grows_with_silence():
    detector = regular(PhiAccrual())
    values = [detector.phi(s) for s in (1.0, 1.2, 1.5, 2.0)]
    assert values == sorted(values) and len(set(values)) == 4


@pytest.mark.parametrize("threshold", [1.0, 3.0, 8.0, 12.0])
def test_horizon_is_where_phi_reaches_the_threshold(threshold):
    detector = regular(PhiAccrual(threshold=threshold, pause=0.5))
    assert detector.phi(detector.horizon()) == pytest.approx(threshold, rel=1e-6)


def test_the_pause_allowance_moves_the_horizon_by_exactly_the_pause():
    base = regular(PhiAccrual()).horizon()
    assert regular(PhiAccrual(pause=3.0)).horizon() == pytest.approx(base + 3.0)


def test_the_spread_floor_applies_when_the_history_is_very_regular():
    assert regular(PhiAccrual(min_std=0.1)).mean_std()[1] == 0.1


def test_a_tiny_floor_turns_a_small_delay_into_certainty():
    tiny = regular(PhiAccrual(window=20, min_std=0.001), count=60)
    sane = regular(PhiAccrual(window=20, min_std=0.1), count=60)
    assert tiny.phi(1.05) > 8.0
    assert sane.phi(1.05) < 1.0


def test_the_window_forgets_old_intervals():
    detector = regular(PhiAccrual(window=10), count=30)
    assert detector.mean_std()[0] == pytest.approx(1.0)
    now = detector.window.last
    for _ in range(10):
        now += 3.0
        detector.heartbeat(now)
    assert detector.mean_std()[0] == pytest.approx(3.0)


def test_the_exponential_variant_scales_with_the_mean_and_ignores_the_spread():
    detector = regular(ExponentialPhi(threshold=8.0), gap=2.0)
    mean, _ = detector.window.mean_std()
    assert detector.horizon() == pytest.approx(8.0 * math.log(10.0) * mean)
    assert detector.phi(detector.horizon()) == pytest.approx(8.0)


def test_an_outage_gap_above_the_cap_is_not_learned():
    capped = regular(PhiAccrual(max_interval=5.0))
    before = capped.mean_std()
    capped.heartbeat(capped.window.last + 60.0)
    assert capped.mean_std() == before
    uncapped = regular(PhiAccrual())
    uncapped.heartbeat(uncapped.window.last + 60.0)
    assert uncapped.mean_std()[0] > 1.5


def test_pekko_logistic_curve_matches_the_normal_curve_near_the_middle():
    detector = regular(PhiAccrual())
    mean, std = detector.mean_std()
    for silence in (1.0, 1.1, 1.2, 1.3):
        assert pekko_phi(silence, mean, std) == pytest.approx(detector.phi(silence), abs=0.1)


def test_threshold_8_sits_about_5_6_deviations_out_on_the_normal_curve_and_5_2_on_pekkos():
    low, high = 0.0, 10.0
    for _ in range(60):
        middle = (low + high) / 2
        if pekko_phi(1.0 + middle, 1.0, 1.0) < 8.0:
            low = middle
        else:
            high = middle
    assert 5.1 < high < 5.3
    assert 5.5 < PhiAccrual(threshold=8.0)._z < 5.7


# --- the trace and the scoring ---------------------------------------------------------------------

def test_a_trace_is_reproducible_from_its_seed():
    first = make_trace([(BUSY, 600.0)], seed=4)
    assert first == make_trace([(BUSY, 600.0)], seed=4)
    assert first != make_trace([(BUSY, 600.0)], seed=5)


def test_heartbeats_reach_the_monitor_in_order():
    trace = make_trace([(BUSY, 3600.0)], seed=6)
    assert trace.arrived == sorted(trace.arrived)
    assert all(later > earlier for earlier, later in zip(trace.sent, trace.sent[1:]))
    assert all(arrival > sent for arrival, sent in zip(trace.arrived, trace.sent))


def test_a_gap_longer_than_the_timeout_is_one_false_alarm():
    trace = Trace(sent=[1.0, 2.0, 3.0, 6.0, 7.0], arrived=[1.0, 2.0, 3.0, 6.0, 7.0], duration=10.0)
    assert score(lambda: FixedTimeout(2.5), trace, start=1.0, end=8.0, crashes=20)["alarms"] == 1


def test_a_gap_exactly_equal_to_the_timeout_is_not_an_alarm():
    trace = Trace(sent=[1.0, 3.5], arrived=[1.0, 3.5], duration=10.0)
    assert score(lambda: FixedTimeout(2.5), trace, start=1.0, end=4.0, crashes=5)["alarms"] == 0


def test_detection_time_is_the_timeout_minus_the_time_since_the_last_heartbeat():
    trace = Trace(sent=[10.0, 11.0], arrived=[10.0, 11.0], duration=200.0)
    result = score(lambda: FixedTimeout(2.5), trace, start=11.0, end=11.0001, crashes=10)
    assert result["mean"] == pytest.approx(2.5, abs=0.001)


# --- the SWIM probe --------------------------------------------------------------------------------

def test_without_loss_a_live_member_is_never_suspected():
    rng = random.Random(1)
    assert all(probe(rng, 0.0, 0) for _ in range(1000))


def test_a_crashed_member_is_always_suspected_however_many_helpers_there_are():
    rng = random.Random(1)
    assert not any(probe(rng, 0.0, 5, target_alive=False) for _ in range(1000))


def test_the_measured_false_positive_rate_matches_the_formula():
    rng = random.Random(3)
    trials = 100_000
    wrong = sum(not probe(rng, 0.2, 1) for _ in range(trials)) / trials
    expected = expected_false_positive(0.2, 1)
    sigma = math.sqrt(expected * (1 - expected) / trials)
    assert abs(wrong - expected) < 4 * sigma


def test_helpers_rescue_a_probe_when_only_the_direct_link_is_dead():
    rng = random.Random(2)
    assert not any(probe(rng, 0.0, 0, direct_link_ok=False) for _ in range(100))
    assert all(probe(rng, 0.0, 3, direct_link_ok=False) for _ in range(100))


def test_round_robin_waits_stay_under_twice_the_group_size_and_random_waits_do_not():
    rng = random.Random(4)
    others = 49
    robin = [wait_for_first_probe(rng, others, "round-robin") for _ in range(20_000)]
    chance = [wait_for_first_probe(rng, others, "random") for _ in range(20_000)]
    assert max(robin) <= 2 * others - 1
    assert max(robin) > others
    assert max(chance) > 2 * others - 1

Here is what the 25 tests pin down. Some check mathematical identities that must hold exactly: φ is log10(2) when the silence equals the mean, and phi(horizon()) returns the threshold. Some check the behaviours from this tutorial: the allowance moves the horizon by exactly the allowance, the floor applies to very regular histories, a tiny floor makes a 50 ms delay look like certainty, the window forgets, and an outage gap above the cap is not learned. Two compare against the logistic curve in Pekko’s source, which agrees with the exact normal curve to within 0.1 near the middle of the range but puts the threshold-8 point about 5.2 spreads out where the exact curve puts it about 5.6, as I said in Step 3. Others check the scoring rules (including that a gap exactly equal to the horizon is not an alarm) and the SWIM probe from Step 7. Run python -m pytest -q:

......................... [100%]
25 passed in 0.18s

Passing tests only prove something if they can fail. mutations.py copies the lab into a temporary folder, plants one bug at a time, and runs the tests against it:

# mutations.py
"""Plant one bug at a time in a copy of the lab and check that the tests notice."""
import glob
import os
import re
import shutil
import subprocess
import sys
import tempfile

HERE = os.path.dirname(os.path.abspath(__file__))
MUTANTS = [
    ("detectors.py", "return mean, max(std, self.min_std)", "return mean, std", "phi: drop the spread floor"),
    ("detectors.py", "y = (silence - (mean + self.pause)) / std", "y = (silence - mean) / std", "phi: ignore the pause allowance"),
    ("detectors.py", "return mean + self.pause + std * self._z", "return mean + std * self._z", "horizon: ignore the pause allowance"),
    ("detectors.py", "if self.max_interval is None or interval <= self.max_interval:", "if True:", "window: learn outage gaps"),
    ("detectors.py", "if len(self.values) > self.size:", "if len(self.values) > self.size + 5:", "window: keep five intervals too many"),
    ("detectors.py", "return self.threshold * math.log(10.0) * mean", "return self.threshold * mean", "exponential: forget the ln(10)"),
    ("evaluate.py", "and arrived[i + 1] - arrived[i] > horizons[i]", "and arrived[i + 1] - arrived[i] >= horizons[i]", "score: count a gap equal to the horizon"),
    ("swim.py", "all(delivered(rng, loss) for _ in range(4))", "all(delivered(rng, loss) for _ in range(3))", "swim: relay with three messages, not four"),
    ("swim.py", "return (others - done) + rng.randrange(others) + 1", "return rng.randrange(others) + 1", "swim: skip the wait for the next traversal"),
]


def run_tests(folder):
    env = dict(os.environ, PYTHONDONTWRITEBYTECODE="1", COLUMNS="170")
    result = subprocess.run([sys.executable, "-m", "pytest", "-q", "-p", "no:cacheprovider"], cwd=folder, env=env,
                            capture_output=True, text=True, encoding="utf-8", errors="replace")
    last = result.stdout.strip().splitlines()[-1] if result.stdout.strip() else "no output"
    failed = re.search(r"(\d+) failed", last)
    return int(failed.group(1)) if failed else 0, last


caught = 0
for number, (name, old, new, label) in enumerate(MUTANTS, 1):
    with tempfile.TemporaryDirectory() as folder:
        for path in glob.glob(os.path.join(HERE, "*.py")):
            if os.path.basename(path) not in ("mutations.py", "run_all.py"):
                shutil.copy(path, folder)
        target = os.path.join(folder, name)
        text = open(target, encoding="utf-8").read()
        assert text.count(old) == 1, f"mutant {number}: expected exactly one match for {old!r}"
        open(target, "w", encoding="utf-8", newline="\n").write(text.replace(old, new))
        failing, summary = run_tests(folder)
    caught += failing > 0
    print(f"mutant {number} ({label}): {'caught, ' + str(failing) + ' tests fail' if failing else 'SURVIVED'}")
print(f"{caught} of {len(MUTANTS)} mutants caught")

Run python mutations.py:

mutant 1 (phi: drop the spread floor): caught, 3 tests fail
mutant 2 (phi: ignore the pause allowance): caught, 4 tests fail
mutant 3 (horizon: ignore the pause allowance): caught, 5 tests fail
mutant 4 (window: learn outage gaps): caught, 1 tests fail
mutant 5 (window: keep five intervals too many): caught, 1 tests fail
mutant 6 (exponential: forget the ln(10)): caught, 1 tests fail
mutant 7 (score: count a gap equal to the horizon): caught, 1 tests fail
mutant 8 (swim: relay with three messages, not four): caught, 1 tests fail
mutant 9 (swim: skip the wait for the next traversal): caught, 1 tests fail
9 of 9 mutants caught

All nine bugs are caught, and several of them were caught by one test only. For example, mutant 7 changes > to >= in the scorer; only the boundary test, with a gap of exactly 2.5 s against a 2.5 s timeout, notices.

Step 7: Ask for a second opinion with SWIM-style probing

Why one observer is not enough

Everything so far has had a single monitor watching a single node. If the path between those two is bad, the monitor accuses a node that everybody else can hear perfectly. SWIM, the protocol described by Das, Gupta and Motivala at Cornell, attacks this by changing who does the checking. In each protocol period, a member picks one other member at random and sends it a ping. If no ack comes back in time, it does not give up. It picks k other members and asks each of them to ping the target for it (a ping-req). If any of those helpers gets an ack and passes it back, the target is fine. Only if all of that fails is the target suspected. The paper explains that relaying through other members avoids “the effect of any congestion on the network path” between the first member and the target. It also claims that “both the expected time to first detection of each process failure, and the expected message load per member, do not vary with group size”, which is the property that makes it scale.

The probe in code

Create swim.py. A probe is one function call, so there are no timers or threads to get wrong:

# swim.py
"""The failure detector half of SWIM: one probe is one function call, so there are no timers and no threads."""


def delivered(rng, loss):
    return rng.random() >= loss


def probe(rng, loss, k, target_alive=True, direct_link_ok=True):
    """One protocol period for one member probing one target.
    True means an ack came back before the period ended, so nobody is suspected."""
    if target_alive and direct_link_ok and delivered(rng, loss) and delivered(rng, loss):  # ping, then its ack
        return True
    for _ in range(k):  # each helper relays four messages: ping-req, ping, ack, ack
        if target_alive and all(delivered(rng, loss) for _ in range(4)):
            return True
    return False


def expected_false_positive(loss, k):
    """Chance that a live target is suspected in one period: the direct ping fails AND all k helpers fail."""
    ok = 1.0 - loss
    return (1.0 - ok ** 2) * (1.0 - ok ** 4) ** k

A direct probe needs two messages to arrive, the ping and its ack. A probe through one helper needs four: ping-req, ping, ack, ack. If each message is lost independently with probability loss, a live target is wrongly suspected only when the direct attempt fails and every one of the k helper paths fails. That gives the formula that expected_false_positive computes:

p_wrong = (1 - (1 - loss)**2) * (1 - (1 - loss)**4)**k

Check the formula against the simulation with step07_swim_probe.py:

# step07_swim_probe.py
import random

from swim import expected_false_positive, probe

rng = random.Random(5)
TRIALS = 200_000
print(f"{'loss per message':>17} {'helpers k':>10} {'wrongly suspected':>18} {'formula':>10}")
for loss in (0.05, 0.10, 0.20):
    for k in (0, 1, 3):
        wrong = sum(not probe(rng, loss, k) for _ in range(TRIALS))
        print(f"{loss:17.2f} {k:10d} {wrong / TRIALS:18.5f} {expected_false_positive(loss, k):10.5f}")

Run python step07_swim_probe.py:

 loss per message  helpers k  wrongly suspected    formula
             0.05          0            0.09753    0.09750
             0.05          1            0.01822    0.01809
             0.05          3            0.00059    0.00062
             0.10          0            0.19048    0.19000
             0.10          1            0.06462    0.06534
             0.10          3            0.00783    0.00773
             0.20          0            0.35836    0.36000
             0.20          1            0.21239    0.21254
             0.20          3            0.07378    0.07409

The simulation matches the formula to within sampling noise. At 10 percent loss per message, a lone ping wrongly condemns a healthy member 19 percent of the time. With three helpers, the rate drops to 0.78 percent. The independence assumption is the weak spot: real losses come in bursts, and one broken link is the case where independence fails completely.

One bad link

Imagine member A cannot reach member B directly, while every other link is fine. A heartbeat monitor on A would suspect B forever. step08_swim_bad_link.py reuses the probe with direct_link_ok=False:

# step08_swim_bad_link.py
import random

from swim import probe

rng = random.Random(9)
TRIALS = 100_000
print("Member A cannot reach member B directly. Every other link works (no loss, then 5 percent loss).")
print(f"{'loss':>5} {'helpers k':>10} {'A suspects B in':>17}")
for loss in (0.0, 0.05):
    for k in (0, 1, 3):
        wrong = sum(not probe(rng, loss, k, direct_link_ok=False) for _ in range(TRIALS))
        print(f"{loss:5.2f} {k:10d} {wrong / TRIALS:16.2%} of periods")

Run python step08_swim_bad_link.py:

Member A cannot reach member B directly. Every other link works (no loss, then 5 percent loss).
 loss  helpers k   A suspects B in
 0.00          0          100.00% of periods
 0.00          1            0.00% of periods
 0.00          3            0.00% of periods
 0.05          0          100.00% of periods
 0.05          1           18.37% of periods
 0.05          3            0.63% of periods

With no helpers, A suspects B in every period. With even one helper and a loss-free network, never. With 5 percent loss, one helper still fails 18.37 percent of the time (a four-message path with 5 percent loss on each message fails about 18.55 percent of the time), and three helpers cut it to 0.63 percent. That is why SWIM’s suspicion step, below, exists: to clean up the mistakes that are left.

Who probes whom

The basic protocol picks each target at random. That has a flaw the paper states plainly: “in the extreme case, this delay could be unbounded as the failed process might never be chosen as a ping target by any other non-faulty process.” The fix in the paper’s Section 4.3 is to walk a shuffled list in order: each member is then probed exactly once per traversal, and the paper bounds the worst-case detection time at about twice the group size. Add the model for both orders to swim.py:

# swim.py (continued)
def wait_for_first_probe(rng, others, mode):
    """Protocol periods from a crash until one survivor first probes the crashed member.
    `others` is how many members a survivor can probe (group size minus one)."""
    if mode == "random":
        wait = 1
        while rng.randrange(others) != 0:  # one pick in `others` lands on the crashed member
            wait += 1
        return wait
    done = rng.randrange(others)  # periods of the current traversal already spent when the crash happens
    slot = rng.randrange(others)  # where the crashed member sits in that traversal
    if slot >= done:
        return slot - done + 1
    return (others - done) + rng.randrange(others) + 1  # it was just probed, so wait for the reshuffled next traversal

The function answers: after a member crashes, how many periods until a survivor first probes it? In random mode, each period is a fresh one-in-others pick. In round-robin mode, the crash lands at a random point in a survivor’s current traversal. If the crashed member’s slot is still ahead, the wait is short. If the survivor just probed it, the wait spans the rest of that traversal plus a position in the reshuffled next one. Run the experiment, step09_swim_order.py, for a group of 50 members:

# step09_swim_order.py
import random

from swim import wait_for_first_probe

MEMBERS = 50
OTHERS = MEMBERS - 1
TRIALS = 3000
rng = random.Random(11)
print(f"{MEMBERS} members, {TRIALS} crashes per mode, waits in protocol periods")
print(f"{'probe order':12} {'first probe, mean':>18} {'first, worst':>13} {'every survivor, mean':>21} {'every, 99th':>12} {'every, worst':>13}")
for mode in ("random", "round-robin"):
    firsts, everys = [], []
    for _ in range(TRIALS):
        waits = [wait_for_first_probe(rng, OTHERS, mode) for _ in range(OTHERS)]
        firsts.append(min(waits))
        everys.append(max(waits))
    everys.sort()
    print(f"{mode:12} {sum(firsts) / TRIALS:18.2f} {max(firsts):13d} {sum(everys) / TRIALS:21.1f} {everys[int(0.99 * TRIALS)]:12d} {everys[-1]:13d}")
print(f"bound for round-robin: 2 x {OTHERS} - 1 = {2 * OTHERS - 1} periods")

Run python step09_swim_order.py:

50 members, 3000 crashes per mode, waits in protocol periods
probe order   first probe, mean  first, worst  every survivor, mean  every, 99th  every, worst
random                     1.59            10                 217.9          422           581
round-robin                1.56             9                  76.8           94            97
bound for round-robin: 2 x 49 - 1 = 97 periods

Look at the two kinds of columns. For the first probe by anyone, both orders are the same, about 1.6 periods. That matches the paper’s claim that the expected time does not depend on group size: with 49 other members, each period has a chance of 1 - (48/49)**49, about 0.636, that somebody picks the crashed one, so the expected wait is about 1/0.636 = 1.57 periods, and for a very large group the limit is e / (e - 1), about 1.58 (my arithmetic). For every survivor to have probed the crashed member, the orders are very different. Random selection takes 217.9 periods on average, 422 at the 99th percentile and 581 in the worst of 3,000 runs. Round-robin averages 76.8, its 99th percentile is 94, and its worst run is 97, which is exactly the lab’s bound, 2 * 49 - 1 = 97. In real SWIM the survivors do not each have to find the failure alone, because the news is piggybacked on ping and ack messages. The ordering matters for the guarantee that every member would find the failure on its own within a bounded time.

Suspicion, incarnation numbers and Lifeguard (explained, not built)

SWIM does not declare a member dead when a probe fails. The paper describes a suspicion step: the member is marked suspected, the news spreads, and after a timeout it is declared failed unless it answers first. In the paper’s words, this timeout “effectively trades off an increase in failure detection time for a reduction in frequency of false failure detections”. A suspected member that is actually alive can refute the rumor by raising its incarnation number, a counter that only that member may increment, and broadcasting that it is alive. The higher incarnation wins, so a stale suspicion cannot overrule a fresh denial.

Suspicion still assumes the observer is healthy. If the observer is the slow one, because its CPU is starved or its queue is full, it will wrongly suspect many others. That is the problem HashiCorp’s Lifeguard extensions address. The abstract of the Lifeguard paper says that slow message processing can cause SWIM to mark healthy members as failed, and proposes extensions that consider “that the local failure detector module may be at fault, via the concept of local health”. HashiCorp’s memberlist library says in its README that it is based on SWIM with extensions, including Lifeguard, and its default LAN configuration probes once a second with a 500 ms probe timeout, three indirect checks and a suspicion multiplier of 4. Consul’s gossip documentation describes the Serf gossip protocol and the Lifeguard enhancements.

How real systems set these numbers

Everything in this table comes from the documentation or source code linked in it, read on the day I wrote this tutorial. Your version may differ, so check yours before copying a number.

Common mistakes, and the check for each

Reading the wall clock

Wall-clock time can jump when the system clock is adjusted, and a jump looks like a long silence. In real code, measure silence with time.monotonic(). The Python documentation describes it as “a clock that cannot go backwards” that “is not affected by system clock updates”. The check: step the system clock on a test machine and confirm that no node is suspected.

Trusting the threshold without measuring it

Step 4 showed a φ of 8 producing one mistake per 780 heartbeats instead of one per hundred million. Replay a few days of your own heartbeat logs through the scorer, as evaluate.py does, and read the false alarm rate directly.

Letting an outage teach the detector

If every silence is added to the window, a node that is misbehaving for ten minutes teaches the detector that long silences are normal, and it stops noticing. Cassandra guards against it. A comment in ArrivalWindow says: “in the event of a long partition, never record an interval longer than the rpc timeout, since if a host is regularly experiencing connectivity problems lasting this long we’d rather mark it down quickly instead of adapting”. The max_interval parameter in this lab does the same, and a test in Step 6 pins it. The check: simulate a 60 s outage and confirm that the mean interval barely moves.

Starting cold

With no history, a detector has nothing to learn from. Pekko seeds the history with made-up intervals around the expected one. Cassandra seeds with a deliberately large first interval, and its source comment explains why: “it’s better to err high (false negatives, which will be corrected by waiting a bit longer) than low (false positives, which cause ‘flapping’)”. The check: start a detector and kill the node during the first minute; the detection time should be long, not zero.

Treating suspicion as death

A suspicion should start a cautious process, not a destructive one. Kubernetes marks an unreachable node’s Ready condition as Unknown and, by default, waits 5 minutes before asking for the first Pod eviction. Anything that would be unsafe if the suspected node were still alive, such as a second leader accepting writes, needs a fence too: see our tutorial on leader election and fencing tokens.

Forgetting that the observer can be the problem

If one monitor reports many failures at once, suspect the monitor first. This is the Lifeguard lesson, and the check is cheap: alert when a single observer’s suspicions jump, before you act on any of them.

Confirm the whole thing works end to end

From the project folder with the virtual environment active, run each step script once, in order, and compare the output with the blocks above. Then run the tests and the mutation check:

$ python -m pytest -q
$ python mutations.py

You should see 25 passed and 9 of 9 mutants caught. The simulated traces and the SWIM experiments use fixed seeds, so every number in the tables should match exactly. The only thing that will differ is how long the commands take. If a number differs, the usual cause is a typo in one of the parameters of CALM or BUSY.

Where to go next

Replace the fake trace with your own data: log the arrival time of every heartbeat for a day, load the list into a Trace, and score your current timeout against φ with and without an allowance. Add the suspicion step by building a small state machine with the three states and the incarnation rule from the SWIM paper, and test it with property-based tests as in our Hypothesis tutorial. Feed the detector’s verdicts into a consistent hash ring so that a node leaves the ring only after its suspicion has timed out. And look at the other tools that protect a service from a slow neighbour: retries with backoff and jitter, a circuit breaker, a bulkhead and load shedding.

Sources

• Hayashibara, Défago, Yared and Katayama, The φ Accrual Failure Detector (JAIST research report IS-RR-2004-010).
• Das, Gupta and Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol (Cornell University).
• Dadgar, Phillips and Currey, Lifeguard: Local Health Awareness for More Accurate Failure Detection (arXiv 1707.00788), and the HashiCorp memberlist README.
• Apache Pekko: PhiAccrualFailureDetector.scala.
• Kubernetes reference pages linked in the table above, and the Python documentation for the time module.