mergedhumanPR #46Transport
Redeem_Grimm: failure-detector layer with a phi-accrual liveness oracle
NANDA Town models failure by injection. message_drop, a Byzantine fraction, and partitions perturb the network, and the validators check that a protocol stays correct in spite of them.
Author
@Redeem-Grimm-Satoshi
github profile →- Status
- Merged
- Merged on
- Jul 8
- Branch
- hackathon/redeem-grimm-failure-detector
Description
The pitch.
## Problem NANDA Town models failure by injection. `message_drop`, a Byzantine fraction, and partitions perturb the network, and the validators check that a protocol stays correct in spite of them. The stack has no vocabulary for the dual question: when should an agent conclude that a peer has stopped responding, and how does it avoid crying wolf on a peer that is merely slow? That decision, the failure detector, is one of the oldest primitives in distributed systems. Chandra and Toueg formalize it in terms of two properties, completeness (every real crash is eventually suspected) and accuracy (a live process is not wrongly suspected), and it is the one classical building block that the twelve-layer stack does not have. The absence is not academic. Several existing scenarios already presuppose that a participant can disappear. `supply_chain` stresses multi-hop reliability under drop and partition, `consensus` needs a quorum to make progress when members are missing, and `contract_net` coordination has to decide what happens when an assignee goes away mid-task. Today the framework can inject that disappearance but cannot let an agent observe it. This PR adds failure detection as a new building block, in the same shape as the existing twelve: a `Protocol` interface, two reference plugins, a scenario that exercises them, and property validators that separate a correct implementation from a plausible but wrong one. ## Persona I work on liveness and membership, so the reference I reached for is the one production systems actually run. Cassandra, Akka, and Hazelcast all ship a phi-accrual detector rather than a fixed timeout, for a concrete reason. A single timeout forces you to trade detection latency against false-positive rate at deploy time, and you lose that bet the moment the network gets jittery: set it tight and you suspect healthy-but-slow peers, set it loose and you are blind to real crashes for too long. An accrual detector defers the decision to the consumer by emitting a continuous suspicion level instead of a boolean, and it adapts that level to the observed inter-arrival distribution. I implemented the real algorithm and, deliberately, a naive fixed-timeout foil, so the layer ships with a built-in demonstration of why the adaptive version earns its keep. ## What is in the diff | Path | Purpose | |---|---| | `packages/nest-core/nest_core/layers/failure_detector.py` | The layer contract. A runtime-checkable `FailureDetector` Protocol: `heartbeat`, `suspect`, `phi`, `report`, `known_peers`. Every method takes `now` as a keyword argument instead of reading a clock, so detection is a pure function of observed history and replays deterministically. | | `.../failure_detection/phi_accrual.py` | The adaptive reference detector. Each peer gets a sliding window of heartbeat inter-arrival samples modeled as a normal distribution; suspicion is `phi = -log10(P(next heartbeat still pending))` from the Gaussian upper tail. It uses population variance, a configurable standard-deviation floor, and a tail-probability floor to keep `phi` finite, and rounds every emitted float to six places. | | `.../failure_detection/heartbeat.py` | The fixed-timeout baseline, included as the foil. Suspects once silence exceeds `timeout`. Cheap, needs no warm-up, and structurally unable to tell a slow peer from a dead one. | | `packages/nest-core/nest_core/scenarios_builtin/failure_detection.py` | The agents and factory. An observer drives one injected detector and publishes a per-peer verdict on each evaluation tick; emitters heartbeat on a jittered interval and broadcast ground-truth `fd:phase` markers; one emitter goes silent for a bounded window and then heals, another is never silent as an always-live control. | | `scenarios/failure_detection.yaml` | The runnable scenario: three agents, the twelve standard layers at their defaults, zero message drop, phi-accrual selected. | | `packages/nest-core/nest_core/validators.py` | Th …
Try it
Open PR on GitHubView diffCheckout locally
git fetch origin pull/46/head:pr-46
git checkout pr-46