Module eventually_perfect_failure_detector 

Eventually perfect failure detection — ◇P.

Status: implementation. Space: bounded by membership. One entry per peer and nothing per message, as the perfect detector has, plus one adaptive delay.

Cachin, Guerraoui & Rodrigues, Module 2.8 and Algorithm 2.7 (“Increasing Timeout”), quoted from the book:

Algorithm 2.7: Increasing Timeout
Implements: EventuallyPerfectFailureDetector, instance ◇P.
Uses: PerfectPointToPointLinks, instance pl.

upon event ⟨ ◇P, Init ⟩ do
    alive := Π; suspected := ∅; delay := Δ;
    starttimer(delay);

upon event ⟨ Timeout ⟩ do
    if alive ∩ suspected ≠ ∅ then
        delay := delay + Δ;
    forall p ∈ Π do
        if (p ∉ alive) ∧ (p ∉ suspected) then
            suspected := suspected ∪ {p};
            trigger ⟨ ◇P, Suspect | p ⟩;
        else if (p ∈ alive) ∧ (p ∈ suspected) then
            suspected := suspected \ {p};
            trigger ⟨ ◇P, Restore | p ⟩;
        trigger ⟨ pl, Send | p, [HEARTBEATREQUEST] ⟩;
    alive := ∅;
    starttimer(delay);

What ◇P is for, and why this repository now needs it

crate::perfect_failure_detector promises if a process is detected, it has crashed — never wrong, never retracted — and is implementable only where a delivery bound Δ is known in advance. ◇P weakens that to eventually, no correct process is suspected, and therefore must be able to take a suspicion back. Restore is the whole difference.

It matters here because a crashed process now comes back. Under P a suspicion is permanent by construction, so Ω’s suspected set only grows, maxrank only ever walks downward through the membership, and a recovered process can never lead again.

alive ∩ suspected ≠ ∅ is the algorithm noticing it was wrong

The guard reads: someone I suspected has been heard from this round. That is a false suspicion caught in the act, and the book’s response is to wait longer next time. Read the negations carefully — an OCR of the page drops them from if (p ∉ alive) ∧ (p ∉ suspected), and taking it as written inverts the algorithm into one that suspects whoever it just heard from.

Departure: the delay comes down again

Algorithm 2.7 adds Δ on every false suspicion and never subtracts. That is a ratchet, and its cost is not the unboundedness but the irreversibility: one bad period leaves detection permanently slower for the rest of the run, long after the network recovered, with nothing reporting that it has.

So after Config::quiet_rounds consecutive rounds in which nothing at all was suspected, the delay comes down by one step — never below Config::min_delay. Down slowly, up fast: the increase is immediate and the decrease waits, and that asymmetry is what damps the oscillation a symmetric rule would produce around the true bound.

“Nothing suspected”, not “nothing withdrawn”, and the difference is the whole rule. The first draft eased off after rounds in which no suspicion was taken back, which is wrong in the worst case: a network bad enough that suspicions are never withdrawn produces no withdrawals at all, so the delay came down while the detector was being consistently wrong. Measured: against a network twelve times the initial delay, the delay drifted back to the floor instead of pinning at the cap. With nothing suspected there is no outstanding claim that could be wrong and the network is evidently keeping up, which is the only situation in which easing off is defensible.

The price is that a genuinely crashed peer, permanently suspected, freezes the delay wherever it had reached. That is deliberate: with a crashed process in the membership there is no clean signal to ease off on, and freezing is strictly better than the ratchet — which grows — and than decreasing blindly, which gets more wrong. A detector that could tell the two apart would be measuring the observed silence of the peers it is not suspecting, which is an accrual detector, and that is the next change rather than this one.

What drives the increase, which is not what you would guess

alive ∩ suspected ≠ ∅ fires when a suspected process is heard from — a false suspicion caught in the act of being corrected. So the delay climbs with the rate at which the detector is caught out, not the rate at which it is wrong. A detector that is consistently wrong, because every peer is beyond the delay every round, is never corrected and never climbs. That is Algorithm 2.7’s own behaviour rather than anything added here, and it is why the increase alone does not converge on a bad network — the cap is what makes the failure bounded and stated.

What it costs: strict eventual accuracy under partial synchrony, where the delay bound is merely finite and unknown. Under a bound that never settles, a detector that can come down can be wrong for ever. What it buys back is accuracy under a weaker and more realistic assumption — that the true delay eventually stops changing — under which the estimate converges and the ratchet does not.

Departure: the delay is capped

delay never exceeds Config::max_delay. Unconditional eventual accuracy needs unbounded growth, because partial synchrony refuses to let you assume any bound in advance — but that is a property of the model rather than of networks, and an operator knows their delay distribution to within orders of magnitude.

Why capping is the right loss. Ask what a wrong ◇P breaks. Ω trusts the wrong leader, which costs an epoch change and an abort — liveness, never safety; leader_driven_consensus states agreement as [always] and termination as already conditional on the detector settling. So a cap that is occasionally too small costs progress during a network episode and clears when the episode does. The uncapped ratchet costs progress permanently, and silently. Both are liveness failures; only one recovers.

Exceeding the cap is the stated condition failing rather than the implementation, exactly as Δ is for the perfect detector — and tests/eventually_perfect_failure_detector.rs makes it happen rather than describing it.

Departure: heartbeats are unsolicited, and the period is not the timeout

Both inherited from crate::perfect_failure_detector, for the reasons its documentation gives: one unsolicited beat per round distinguishes the same failures in half the messages of a request/reply exchange, and separating the beat period from the silence a peer is allowed stops a single missed round being fatal. Here the timeout is what adapts; the period does not.

◇P1 [always]      Strong completeness — every crashed process is eventually permanently
                  suspected by every correct process
◇P2 [Δ ≤ max_delay ∧ Δ eventually stable]
                  Eventual strong accuracy — eventually no correct process is suspected

◇P2’s scope is the two departures above, written down. The same shape as PB2 [window] and SL1 [session]: the guarantee is conditional and the condition is named, rather than the guarantee being quietly weaker than the page’s.

Structs

Config

How this detector beats, waits and adapts.

EventuallyPerfectFailureDetector

Detects crashes by heartbeat timeout, and changes its mind.

Enums

Ind

Indications to the layer above.

Type Aliases

Cmd

Requests from the layer above: none, as Module 2.8 has it.