How do distributed systems detect node failures?

// Failure detection on a fake clock (ms). Heartbeats every 1000 ms with jitter.
// Node B is alive but has a 3.5 s GC pause at t=20 s; node C crashes at t=29.5 s.
const JIT = [0, 40, -30, 120, 10, -60, 80];
const END = 40000;
function beats(node) {
  const out = [];
  for (let k = 0; k * 1000 < END; k++) {
    const t = k * 1000 + JIT[k % 7];
    if (node === "B" && t >= 20000 && t < 23500) continue; // paused: sends nothing
    if (node === "C" && t >= 29500) break; // crashed
    out.push(t);
  }
  if (node === "B") out.push(23500), out.sort((a, b) => a - b); // first beat after the pause
  return out;
}

function fixedTimeout(arrivals, timeoutMs) { // checked every 100 ms
  let i = 0, last = -Infinity, suspected = false, episodes = 0, firstAt = null;
  for (let now = 0; now <= END; now += 100) {
    while (i < arrivals.length && arrivals[i] <= now) { last = arrivals[i++]; suspected = false; }
    if (!suspected && last > -Infinity && now - last > timeoutMs) { suspected = true; episodes++; if (firstAt === null || now > 29500) firstAt = now; }
  }
  return { episodes, firstAt };
}

console.log("== 1. Fixed timeout: speed vs false positives ==");
console.log("timeout   B (alive) false suspicions   C (crashed at 29.5 s) detected   delay");
for (const T of [1100, 1500, 3000, 5000]) {
  const b = fixedTimeout(beats("B"), T), c = fixedTimeout(beats("C"), T);
  console.log(`${String(T).padStart(5)} ms ${String(b.episodes).padStart(26)} ${String(c.firstAt / 1000).padStart(25)} s ${String((c.firstAt - 29500) / 1000).padStart(6)} s`);
}

// Phi accrual: phi = -log10(P(next heartbeat is later than now)), normal model of intervals.
function erfc(x) { // Numerical Recipes erfcc, fractional error < 1.2e-7
  const z = Math.abs(x), t = 1 / (1 + 0.5 * z);
  const r = t * Math.exp(-z * z - 1.26551223 + t * (1.00002368 + t * (0.37409196 + t * (0.09678418 + t * (-0.18628806 + t * (0.27886807 + t * (-1.13520398 + t * (1.48851587 + t * (-0.82215223 + t * 0.17087277)))))))));
  return x >= 0 ? r : 2 - r;
}
function stats(intervals) {
  const mean = intervals.reduce((s, x) => s + x, 0) / intervals.length;
  const sd = Math.sqrt(intervals.reduce((s, x) => s + (x - mean) ** 2, 0) / intervals.length);
  return { mean, sd };
}
const phi = (elapsed, { mean, sd }) => -Math.log10(0.5 * erfc((elapsed - mean) / (sd * Math.SQRT2)));

console.log("\n== 2. Phi accrual: the same threshold adapts to each network ==");
const nets = [["LAN (jitter x1)", 1], ["cross-region (jitter x5)", 5]];
for (const [name, scale] of nets) {
  const iv = [];
  for (let k = 0; k < 70; k++) iv.push(1000 + scale * (JIT[(k + 1) % 7] - JIT[k % 7]));
  const s = stats(iv);
  const cross = [1, 3, 8].map((th) => { let e = 0; while (phi(e, s) < th) e += 10; return `phi>=${th} at ${e} ms`; });
  console.log(`${name.padEnd(25)} mean=${s.mean.toFixed(0)} sd=${s.sd.toFixed(1)}  ${cross.join(", ")}`);
}
const lan = stats(Array.from({ length: 70 }, (_, k) => 1000 + JIT[(k + 1) % 7] - JIT[k % 7]));
console.log(`LAN phi after silence: ${[1100, 1200, 1300, 1500, 2000].map((e) => `${e} ms -> ${Math.min(phi(e, lan), 99).toFixed(2)}`).join(", ")}`);

console.log("\n== 3. SWIM-style probing: indirect pings and suspicion ==");
const reach = (a, b, down, broken) => !down.has(b) && !broken.has(`${a}-${b}`);
function probe(target, down, broken, helpers) {
  if (reach("A", target, down, broken)) return "ack (direct)";
  const via = helpers.filter((h) => reach("A", h, down, broken) && reach(h, target, down, broken));
  return via.length ? `ack via ${via.join(",")} (indirect)` : "no ack";
}
const helpers = ["B", "C", "E"];
let down = new Set(), broken = new Set(["A-D"]);
console.log(`link A-D drops packets, D is fine. direct-only: ${reach("A", "D", down, broken) ? "alive" : "D marked DEAD (false positive)"}`);
console.log(`SWIM, k=3 helpers: A probes D -> ${probe("D", down, broken, helpers)} -> D stays ALIVE`);

// Membership entries {status, inc}. Merge rule: higher incarnation wins; at equal
// incarnation SUSPECT beats ALIVE; CONFIRM (dead) beats everything.
const rank = { ALIVE: 0, SUSPECT: 1, CONFIRM: 2 };
function merge(cur, msg) {
  if (cur.status === "CONFIRM") return cur;
  if (msg.status === "CONFIRM" || msg.inc > cur.inc || (msg.inc === cur.inc && rank[msg.status] > rank[cur.status])) return msg;
  return cur;
}
const show = (e) => `${e.status}/${e.inc}`;
down = new Set(["D"]); broken = new Set();
let viewA = { status: "ALIVE", inc: 0 }, viewC = { status: "ALIVE", inc: 0 };
console.log(`D pauses (GC):     A probes D -> ${probe("D", down, broken, helpers)}`);
viewA = merge(viewA, { status: "SUSPECT", inc: 0 });
console.log(`  A marks D ${show(viewA)} and gossips it`);
down = new Set();
const refute = { status: "ALIVE", inc: 1 }; // D hears the rumour about itself and bumps its incarnation
viewA = merge(viewA, refute); viewC = merge(viewC, refute);
console.log(`  D resumes, gossips ${show(refute)}: A sees ${show(viewA)}, C sees ${show(viewC)}`);
viewC = merge(viewC, { status: "SUSPECT", inc: 0 });
console.log(`  a late SUSPECT/0 reaches C: C keeps ${show(viewC)} (stale rumour ignored)`);
down = new Set(["D"]);
viewA = merge(viewA, { status: "SUSPECT", inc: 1 });
console.log(`D crashes:         A probes D -> ${probe("D", down, broken, helpers)} -> A marks ${show(viewA)}`);
const period = 3; // suspicion timeout: 3 protocol periods pass with no refutation
viewA = merge(viewA, { status: "CONFIRM", inc: 1 });
console.log(`  no refutation after ${period} periods -> ${show(viewA)} (dead, removed from membership)`);

console.log("\nmessages per protocol period (k=3 helpers, worst case every probe goes indirect):");
for (const n of [10, 100, 1000])
  console.log(`  N=${String(n).padEnd(5)} all-to-all heartbeats ${String(n * (n - 1)).padStart(7)}   SWIM <= ${String(n * (2 + 4 * 3)).padStart(6)}   (per member: ${n - 1} vs <= ${2 + 4 * 3})`);