Beyond the Binary Timeout

Traditional failure detection uses a fixed timeout (e.g., "If no heartbeat for 5 seconds, mark dead").

• Problem: In an unstable network (cloud), latency spikes. A fixed timeout is either too aggressive (false positives) or too slow (slow detection).

The Phi ($\varphi$) Accrual Failure Detector, introduced by Hayashibara et al. in 2004, solves this by making the timeout adaptive.

How it Works

Instead of a binary state (Up/Down), the detector outputs a continuous value, $\varphi$ (Phi), representing the suspicion level.

Where $P_{later}$ is the probability that a heartbeat will arrive later than the current time, given historical mean and variance.

The Scale

The Algorithm

1. Sampling: Every time a heartbeat arrives, store the arrival time in a sliding window (e.g., last 1000 samples).
2. Statistics: Calculate the Mean ($\mu$) and Variance ($\sigma^2$) of the arrival intervals.
3. Distribution: Assume arrival times follow a Normal Distribution (Gaussian).
4. Calculation: When checking for failure at time $t_{now}$:
   • Time since last heartbeat: $t_{diff} = t_{now} - t_{last}$
   • Calculate probability $P$ that a value $x > t_{diff}$ exists in the distribution.
   • $\varphi = -\log_{10}(P)$

Real World Example: Cassandra

Apache Cassandra uses Phi Accrual to detect down nodes.

• By default, phi_convict_threshold is set to 8.
• This means Cassandra waits until the chance that "it's just slow" is less than $10^{-8}$ before declaring a node dead.
• Benefit: If EC2 network gets laggy, the mean and variance increase. The algorithm automatically relaxes the timeout. When network stabilizes, it tightens up.

Visualizing the Windows

Imagine two scenarios:

Scenario A: LAN (Stable)

• Heartbeats arrive every 100ms $\pm$ 2ms.
• Statistical variance is low.
• If a heartbeat is missing for 200ms, $\varphi$ shoots up to 10+ instantly. Fast detection.

Scenario B: WAN (Jittery)

• Heartbeats arrive every 100ms $\pm$ 50ms.
• Statistical variance is high.
• If a heartbeat is missing for 200ms, $\varphi$ might only be 1.5. The system "knows" this network is noisy and waits longer. Robutness.

Implementation Note

While the original paper assumes Normal Distribution, some implementations (like Akka) simplified this or use exponential distribution approximations to avoid expensive integral calculations in the hot loop.

import math

class PhiDetector:
    def __init__(self, threshold=8.0):
        self.threshold = threshold
        self.intervals = [] # sliding window
    
    def heartbeat(self):
        now = time.time()
        if self.last_time:
            self.intervals.append(now - self.last_time)
        self.last_time = now
        
    def is_available(self):
        phi = self._calculate_phi()
        return phi < self.threshold