Size the successor list and stabilization period from network estimates (RFC 7363) instead of a fixed r = 3

[zkjoie]

Motivation

The successor list is the only structure Chord's correctness depends on; fingers are an optimisation (docs/src/advanced-topic/chord.md). Rings fixes its length at dht_succ_max = 3 (crates/core/src/swarm/builder.rs, DEFAULT_SUCCESSOR_CAPACITY in crates/core/src/dht/topology.rs) and every entry must be an admitted transport (TopoInfo::confirmed_by).

Two results bound what r = 3 can survive:

• Stoica et al., "Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications" (IEEE/ACM ToN 2003), Theorem IV.5: with r = Ω(log N) successors, a ring in which every node fails independently with probability 1/2 stays connected with high probability. r = 3 gives no such guarantee at any N.
• Zave, "How to Make Chord Correct" (arXiv:1502.06461): correctness requires a stable base of r + 1 nodes that never leave; with r = 3 that base is four nodes, which a browser-majority overlay cannot promise.

Concretely, when a node's three successors all disappear inside one detection window (silent failure is detected only after PEER_LIVENESS_IDLE_MS 15 s + PEER_LIVENESS_TIMEOUT_MS 45 s, crates/core/src/swarm/transport/liveness.rs), SuccessorSeq::min() returns self, find_successor answers Local(self), and the node is out of the ring. With a residual session time τ per successor and window W the per-node probability is (1 − e^{−W/τ})^r:

τ	r = 3	r = 8	r = 16
5 min	6·10⁻³	1·10⁻⁶	1·10⁻¹²
30 min	7·10⁻⁶	2·10⁻¹³	≈ 0

Browser session lengths are heavy-tailed with medians of minutes (Stutzbach & Rejaie, "Understanding Churn in Peer-to-Peer Networks", IMC 2006: Weibull, k ≈ 0.34–0.38), so the first row is the relevant one.

The stabilization period is fixed too (DEFAULT_STABILIZE_INTERVAL = 15 s, native and browser alike, crates/node/src/native/config.rs, frontend/src/app.rs), with no jitter. Liben-Nowell, Balakrishnan & Karger, "Analysis of the Evolution of Peer-to-Peer Systems" (PODC 2002) show the stabilization rate must scale with log N per half-life for the ring to stay consistent; a constant period is either wasteful in a quiet overlay or too slow in a churning one.

Proposal

Adopt the self-tuning scheme of RFC 7363 ("Self-Tuning Distributed Hash Table for RELOAD"), §6, which needs only state Rings already has:

1. Estimate N from successor/predecessor density: N = 2^160 / d, d = mean inter-peer distance across the known successor list and predecessor (RFC 7363 §6.1; accurate within ~15 %).
2. Estimate the failure rate U = k / (M · T_k) from Disconnected events in the measurement ledger (crates/measure), where k failures were observed among M distinct peers over T_k (§6.3).
3. Size the successor list as max(3, ⌈log₂ N⌉) (§6.2), keeping dht_succ_max as a lower bound rather than the value. Successors are connections, so this also raises the retained-connection budget by the same term (RETAINED_CONNECTIONS_PER_REFERENCE_SLOT, crates/core/src/swarm/transport/retention.rs).
4. Derive the stabilization period T_stab = min(1/(2U) / log₂²N, N/(L · log₂²N)) with the RFC's 15 s floor (§6.6), and add ±10 % jitter to every periodic phase so fleets do not synchronise (Rhea et al., "Handling Churn in a DHT", USENIX 2004, §3).
5. Exchange estimates with a few random finger peers and take the 75th percentile (§6.5), so a node with a short list does not under-estimate N.

Acceptance

• r grows with the N estimate; a deterministic test shows a 3-node ring keeps r = 3 and a 1 000-node model uses r = 10.
• Losing all r successors inside one window is bounded by the table above under the churn simulator (tracked separately).
• The stabilization period and jitter are derived, not configured, with the configured value acting as a floor.
• SECURITY.md Layer Contracts and docs/src/advanced-topic/chord.md state the r + 1 stable base in terms of the adaptive r.

Related

• Automatic re-join when the list empties is a separate issue (persisted peer cache); Add run-owned bootstrap reachability and automatic redial #763 covers native seed redial.
• Finger convergence is Avoid linear 160-round finger-table convergence #768 / Bound finger-table convergence by proved ranges #770 and is unaffected by r.

Issue family (browser-churn stability, 2026-09-14)

#773 churn simulator · #774 adaptive successor list and stabilization period · #775 age-ranked peer cache and re-join · #776 RTT-derived timeouts, ICE restart, lookup retry · #777 inbox replication and Leave · #778 stability-weighted storage · #779 browser lifecycle events. Finger convergence is #768 / #770; native seed redial is #763.