-
Notifications
You must be signed in to change notification settings - Fork 104
leios conditional diffusion
Yves Hauser's §5.6 extension to the Leios ΔQ report (his notebook
analysis.ipynb on branch yveshauser/improved-deltaq-notebook in
ouroboros-leios; our framing / derivation write-ups of it are
5.6-full-diffusion-framing-draft.md
and
5.6-conditional-derivation-walkthrough.md)
answers a specific network-safety question:
Given that an EB was certified at the voter deadline $t_v = 7\text{ s}$, what is the probability that all $N = 2500$ honest nodes have received the EB body by the end of the round at $t = 14\text{ s}$?
Linear Leios inherits from Full Leios a network-safety property: certification of an EB implies its body has reached every honest node in time for the next round. If this doesn't hold, honest nodes can fall behind the certified chain state, breaking Praos timing assumptions. §5.6 quantifies the probability of that property holding in the ΔQ model.
The 14 s is not a hard wall. A certificate is
includable only if the next RB arrives ≥ 14 slots after the
announcing RB (CIP inclusion rule), so the binding constraint is
next-RB arrival, and CIP Constraint 2 bounds full transmission
against next-RB processing with some slack. A node that misses
recovers via MsgLeiosBlockRangeRequest — at the cost of delaying its
own chain adoption (the certified-EB "urgency inversion",
CIP:1193-1198), not an instant safety break. So
This document records how our branch's mux telemetry supports that
analysis — measurement of the formula's inputs, direct validation of
its output on a testnet, and runtime-adaptive levers derived from the
formula's structure. Companion to
leios-overlap.md,
leios-testnet.md, and
leios-report-gaps.md.
The closed-form result:
In plain English. The numerator is the joint probability that all
$N$ nodes arrived by
Where:
-
$G(t)$ = the per-node EB-body arrival CDF from multi-hop diffusion. This iscdf_blended_delay(s_eb_body_kb)in Yves's notebook — itself a convolution of a per-hop transfer-time CDF (parameterised by Mathis or CUBIC at assumed$p$ and RTT bins) with a path-length distribution (regular random graph, 2500 nodes, degree 10, in the current implementation). -
$N = 2500$ — honest nodes. -
$M = 600$ — committee voters. -
$\tau = 0.75$ — quorum threshold. -
$t_v = 3L_{\text{hdr}} + L_{\text{vote}} = 7\text{ s}$ — voter deadline. -
$t = L_{\text{total}} = 14\text{ s}$ — round end. -
$P(C) = \overline{B}(\lceil\tau M\rceil-1;, M,, G(t_v))$ — marginal certification probability.
At the report's default parameters:
However, the 1.000 is body-only and honest-case.
Body-only:
Modelling assumptions. Yves's derivation lists six explicit caveats:
-
i.i.d. arrivals across nodes — real arrivals are positively
correlated (shared paths, common bottlenecks). Makes the formula
pessimistic: true
$F_{\text{full}\mid C}$ is larger. - Committee size fixed at $M = 600$ — real Leios uses stake-weighted Poisson sortition. The bias largely cancels in the numerator/denominator ratio.
- $G$ scope is EB body only — the 12 MB closure needs a different formulation (the Closure coverage section covers that separately).
-
Stake-independent hop count — if larger SPOs are systematically
better-connected, committee oversamples fast nodes and the formula
is optimistic: true
$F_{\text{full}\mid C}$ smaller. Opposite direction from caveat 1. - Comparison to Coretti et al. 2025 Lemma 7 is by analogy — the formula is a fresh ΔQ-model derivation.
- No Monte Carlo cross-validation in Yves's version.
Which caveats our machinery addresses. Caveats 1, 3, 4 are addressable by measurement — 1 and 4 via the per-EB arrival log (see below), 3 via the Closure coverage section (which also touches our tx-submission machinery). Caveats 2 and 5 sit outside our machinery: caveat 2 is a sortition-randomness question (network telemetry doesn't observe committee-selection bias), caveat 5 is a theoretical question (whether Lemma 7's analogy holds is not a measurable property). Caveats 1 and 4 have opposite directional biases that partially cancel; the measurement campaign lets us quantify each independently and see which dominates.
§5.6's
Yves's notebook answers the closure question at the feasibility level
(its §5.2/§5.3 — can the network deliver the closure in time), rather
than as a conditional
-
1-hop (each node fetches only its missing
$\pi_1$ fraction from an upstream peer):$P(\le 7\text{ s}) \approx 0.933$ Mathis /$0.999$ CUBIC — feasible under either throughput model. -
Full-blended (worst case: the closure is not pre-diffused, so the
whole 12 MB traverses the multi-hop mesh):
$P(\le 14\text{ s}) = 0.139$ Mathis /$0.991$ CUBIC — Mathis fails, CUBIC essentially succeeds on network delivery alone.
Each node fetches only the closure's missing fraction (miss rate
-
Honest pre-diffusion failure (low
$\alpha$ ): the closure isn't pre-diffused, so it is a worst-case blended fetch. -
Adversarial withholding (the
$G_{\text{adv}}$ / T22 case
above): the producer serves non-voters nothing, so their only
closure source is post-certification re-diffusion inside the tight
$L_{\text{diff}}$ window.
So closure coverage is comfortable in the honest baseline
(pre-diffusion working) and binds precisely in the degraded and
adversarial regimes — the same ones where
Measurement. Log closure-completion times (not just body
arrivals) at every node; the per-EB arrival log of
leios-priority-measurement.md must
carry a closure-complete timestamp per node per EB. The informative
comparison is closure completion under honest conditions
(pre-diffusion working, expected ≈ the 1-hop bound) versus under
induced pre-diffusion failure
or a T22 injection (expected to fall toward the full-blended bound) —
the same experiment as
§5.6's
This is not a corner case; it is the scenario the CIP's
$G_{\text{adv}}(t)$ — the CDF of the 12 MB closure reaching the whole mesh, starting from an adversary-chosen ~25%-of-nodes seed set, within$L_{\text{diff}} = 7$ s.
Computing it is a small modification of Yves's machinery: replace the single-origin per-hop convolution with a multi-source diffusion seeded from a random (baseline) or worst-case-clustered (adversarial) 25%-node set, and evaluate the all-arrived probability over the remaining 75% in a 7 s window — a seeded percolation rather than a single expanding front.
Measuring it is a clean testnet injection (see
leios-testnet.md's campaign adversarial menu):
a producer that serves the closure only to a configured voter subset,
with
The seed-egress corollary. Even in the honest case, the seed-hop
story concentrates load: ~76% one-hop coverage means ~1,900 nodes pull
12 MB from big-ledger seeds within ~3 s, and stake-weighted selection
points them at the largest pools. A top pool that is a big-ledger peer
of ~50 nodes must serve ~600 MB in a ~3 s burst ≈ 1.6 Gbps — plausibly
the binding constraint before any per-hop TCP effect the report models,
and a simple division nobody has done. Under
Our tracing produces empirical replacements for the formula's inputs.
Every response burst on the testnet gives one per-hop throughput
sample (bytes-per-second on that hop under the actual congestion
regime, actual
Coverage note: estBurstS supplies the throughput slope; the RTT
distribution (per-peer, from PeerRTT.quantile) supplies the timing
base — slow-start round durations and steady-state ACK-clocking.
Together they define per-hop transfer-time as a function of message
size, which is what the convolution needs.
The convolution's other input. Two complementary sources, per gap 3
of leios-report-gaps.md:
-
Topology survey: pseudo-mainnet dataset in
ouroboros-leios/data/simulation/pseudo-mainnetand analysis notebookcfd.ipynb. Preliminary read shows degree ~30 and diameter 6 hops — the report's degree-10 regular-random-graph baseline is empirically divergent. -
Reconstruction from live diffusion: cross-node correlation of
per-EB arrival events on a testnet (
leios-testnet.md's "What requires cross-node correlation" section). Produces the actual path-length distribution during EB diffusion, which may differ from shortest-graph-paths due to peer-selection preferences.
Both plug into
Yves's caveat 1 says the i.i.d. assumption is pessimistic. Our measurement can quantify by how much:
- Log per-EB arrival times at every measurement node (same log needed for reconstruction).
- Compute empirical correlation between
$T_i$ and$T_j$ for pairs of nodes (across the EB population). - Illustratively — the actual thresholds depend on how close
$G(14)$ is to 1:- Low correlation (~0.1): i.i.d. is close to reality; formula's pessimism is minimal.
- High correlation (~0.5): formula meaningfully understates
$F_{\text{full}\mid C}$ .
This is also exactly gap 2 of leios-report-gaps.md — cross-node
correlation silently assumed lockstep. Yves's §5.6 is a specific
downstream consumer of what gap 2 asks us to measure.
Cross-reference stake distribution against observed per-node arrival times. If large SPOs are systematically 2× faster than mainstream ones, the formula is optimistic in caveat 4's direction. Empirical bias direction and magnitude are measurable from the same per-EB arrival log plus the public stake distribution.
The formula's output is directly measurable — we don't have to validate only the inputs. Recipe:
-
Per-EB arrival logging across the mesh. Same log required for
gap 3's reconstruction:
(node, EB_id, arrival_ts)for every EB at every measurement node. -
Certification outcome per EB. From
cardano-tracer's block-diffusion / EB-certification traces. -
Empirical joint distribution. For each EB
$j$ (indexing over the EB population; the per-node index$i$ from Yves's formula is still there, now as a superscript):-
$C_j$ = certification-succeeded flag -
$T_j^{(1)}, \ldots, T_j^{(N)}$ = per-node arrival times for this EB - Compute whether
$\max_i T_j^{(i)} \le 14\text{ s}$ .
-
- Empirical estimator.
- Compare to Yves's formula. If $\hat{F}{\text{full}\mid C}(14) \approx 1.000$, the headline result is validated. If systematically lower, either the formula's assumptions are wrong (revisit caveats 1 and 4) or the mesh is worse than the report's default parameters suggest. Note this validates only the body-only, honest-case headline; closure coverage and the adversarial $G{\text{adv}}$ are separate measurements requiring closure-complete timestamps and a T22 injection respectively (see those sections).
At
Caveat — independence. These counts assume independent rounds. If
failures cluster (gap 4 autocorrelation, or the livelock cascade), the
effective independent sample size is smaller than leios-testnet.md), so report
Three definitional points the empirical estimator needs pinned down, or it is biased for boring reasons:
-
Eligibility filter (node churn). "All
$N$ honest nodes by 14 s" is ill-defined while nodes restart, sync, or briefly partition — such a node "misses" for reasons unrelated to diffusion, biasing$\hat{F}$ low. Count a node toward a round only if it was up and chain-synced at that round's start (from its own join/sync traces), and report$\hat{F}$ over eligible nodes; state the filter so the number is reproducible. -
$N$ -sensitivity.$F$ is$G(t)^N$ — exponentially sensitive to the node count right where the headline lives. At per-node$P(\text{by }14\text{ s}) = 0.9999$ , the all-arrived probability is$0.9999^{2500} \approx 0.78$ but$0.9999^{10000} \approx 0.37$ : same per-node CDF, very different headline, purely from$N$ . The report uses$N = 2500$ ; the calibrated pseudo-mainnet has 10 000. Always report$\hat{F}$ with its$N$ , and compare to the formula at the same$N$ the testnet ran — never a 100-node$\hat{F}$ against a 2500-node analytical$F$ . -
NTP skew vs same-region hops.
$\hat{F}$ itself only needs each node's local "arrived by my 14 s", which is skew-tolerant. But the path-length reconstruction on the same log infers forwarders from cross-node arrival ordering, and same-region hops (6–35 ms) are comparable to inter-host NTP skew (1–10 ms), so within-cluster ordering can invert (cross-region ordering is safe — the ~130 ms gap swamps skew). Fix: tight sync (PTP / chrony) on measurement nodes, or recordarrived_from_peerdirectly (seeleios-priority-measurement.md) so ordering isn't inferred from timestamps at all.
-
Slowest-node identity and its temporal structure. For each certified EB
$j$ , record$\arg\max_i T_j^{(i)}$ (the round's slowest node) and analyse the pattern across EBs. Three qualitatively different regimes are possible — the same three the LeiosFetch analysis names in its marginal-vs-joint discussion (seeleios-fetch-scheme.md's "What remains uncertain") — each implying a different intervention shape:- Persistent. Same handful of nodes are slowest repeatedly across rounds; identify the persistently-slow subset for peer-selection or operator review. Targeted per-node intervention pays off.
- Rotating. Slowest-node identity varies per round with no stable slow subset. Per-node targeting has no stable target; per-round-adaptive levers (voter self-throttle, adaptive body sizing) apply instead.
- Bimodal (churn-induced). Per-round-type structure rather than per-node — dense-origin rounds see fast completion, sparse-origin rounds see systematically slower completion, with orphaning approximately uniform across nodes within a sparse-origin round. Targeted big-ledger churn (Improvement #8 in leios-fetch-scheme.md) is a specific per-round-type countermeasure.
Empirical disambiguation comes from computing
$\hat{F}_{\text{full}\mid C}(14)$ split by round type (seeleios-testnet.md's churn-tendency measurement recipe, item 7) and counting orphan-set overlap across rounds. Reality is likely mixed — mostly rotating/bimodal with a small persistent tail from unlucky peer draws, poor hardware, or bad network position. -
G(t)-empirical vs G(t)-modelled. Plot the empirical CDF of per-node arrival times against the modelled
$G(t)$ at each body size. Divergence tells us whether$G$ is over- or under-estimated, and where in the tail the discrepancy lives. -
Correlation matrix. Cluster nodes by peer graph, compute within-cluster vs between-cluster arrival correlation. Directly validates caveat 1's magnitude.
The formula makes clear what "improving the odds" means:
Applicable only when the persistent regime dominates. Per the
three-regime distinction described under Slowest-node identity
and its temporal structure
above, the empirical distribution of
- Persistent regime. Same nodes are slowest across rounds (unlucky peer draw that hasn't recovered, bad network position, poor hardware, cold-connection dynamics). Per-node intervention pays off. This is where slowest-node targeting is high-leverage.
- Rotating regime. No stable slow subset — the lever doesn't apply; use per-round-adaptive levers (2, 3, 4) instead.
-
Bimodal regime. Structure is per-round-type rather than
per-node; sparse-origin rounds see systematically worse
mesh-wide
$\hat{F}_{\text{full}\mid C}(14)$ . Targeted big-ledger churn (Improvement #8 in leios-fetch-scheme.md) is the specific per-round-type countermeasure, not per-node targeting.
The measurement path in
leios-testnet.md disambiguates. Reality is
likely mixed — mostly rotating/bimodal with a small persistent
tail — so this lever's applicability depends on the empirical
persistent fraction.
When the persistent regime applies:
- Peer-selection at slow nodes could be biased toward well-connected hubs (shorter effective paths).
- The operator can be alerted (kernel tuning, connection diversity, bandwidth).
-
When the empirical tail sits close to the deadline — i.e.,
when
$G(14)$ is meaningfully below 1 and the slowest nodes are what's dragging it down — reducing$\max_i T_j^{(i)}$ by a second on the slowest 1 % of nodes shifts$G(14)^N$ far more than the same reduction on$\mathbb{E}[T_i]$ across the whole mesh. At the report's default parameters where$G(14) \approx 1$ already, neither intervention has room to help.
This is a coordination problem — no single node can identify itself as "the slowest"; it requires cross-node visibility from the trace consumer. But once identified, the intervention is per-node.
Yves's formula gives the quantitative justification for how much
improvement each 100 kB shave off the EB body buys, via its
dependence on
A block producer that observes (via its own peer window) that mesh
health is degraded can voluntarily cap the EB body below 512 kB —
reducing G(t)'s tail. This is the "adaptive leios-testnet.md's reader-view expansion, now
with a specific analytical measure of what to trade against.
This lever is also the mesh's stabilizing feedback against
sustained-overload livelock, per
leios-testnet.md's "Cascade to livelock"
section: TxCache amortizes retry cost but doesn't add capacity, so
under sustained certification failure it's this lever — not
TxCache — that reduces per-round load until certification recovers.
That section carries the collapse-threshold and loop-stability
measurement recipes.
This lever is structurally different from 1, 2, 4, 5: it does not
improve
Trigger: a voter observing its own EB arrival approaching
Runs into the observation-manipulation attack surface (Proposal A of
threat-model-additions.md) — voters that self-throttle based on
observations can be targeted by observation-inflating adversaries.
Median-based aggregation and hysteresis apply.
As its 14 s budget runs down without the EB body, a node can
(re)direct the fetch at the peer likeliest to deliver fastest — the
one that announced the header earliest (header precedes body), refined
by observed PeerRTT / estBurstS — and prioritise this EB over older
or lower-value fetches competing for the same downlink. Concretely:
reissue the LeiosFetch MsgLeiosBlockRequest to the fastest-observed
peer and bump its priority, improving
The path-length distribution feeding
-
Prefer close peers (short RTT, likely same region). Better
$G$ under normal conditions, worse under partition. - Prefer diverse peers (different ASN, different region). Worse per-hop RTT but better resilience.
Yves's formula doesn't tell us which is right — but it gives a
quantitative framework for comparing the two under measured
Yves's §5.6 is a downstream consumer of several gaps in
leios-report-gaps.md, not a new gap of its
own:
- Gap 2 (cross-node correlation) — Yves's caveat 1 is the same observation. Fixing gap 2 (measuring correlation) directly quantifies the caveat.
-
Gap 3 (path-length distribution) —
$G(t)$ 's convolution depends on this. Fixing gap 3 (topology survey + reconstruction) directly improves$G$ 's fidelity. -
Gap 5 (per-node interface contention) — not in Yves's
formulation; affects
$G$ in real deployments and would show up in the empirical-vs-modelled$G$ comparison. -
Gap 8 (uncertainty envelope) — Yves lists 6 explicit caveats
with directional biases. Under an uncertainty-envelope regime,
$F_{\text{full}\mid C}$ carries a confidence interval derived from those caveats.
Not covered by §5.6. Yves's formula is single-round: it treats
one certification event in isolation. Multi-round dynamics —
cascading feedback from a heavy round that consumes mesh bandwidth,
oscillatory recovery after a failure — are outside the scope of the
formula and its empirical estimator. That's gap 4 of
leios-report-gaps.md (round-to-round feedback and recovery
dynamics), addressed by a separate multi-round measurement or
simulation.
The measurement campaign that closes gaps 2, 3, 5 also directly serves Yves's §5.6.
-
Closure coverage. Treated in its own section,
Closure coverage. Yves's notebook gives the
closure feasibility bounds (§5.2/5.3); with the missing fraction
small under normal pre-diffusion the 1-hop bound is the baseline, and
the full-blended bound applies under pre-diffusion failure or
adversarial withholding.
Measurement need: a closure-complete timestamp per node per EB (not
just body arrival); relevant transport signal is per-mini-protocol
DeltaQ on LeiosFetch (
MsgLeiosBlockTxsRequest), with tx-in-mempool the complementary tx-submission signal. -
What
$F_{\text{full}\mid C}$ looks like under stress. The formula gives ~1.000 at the report's default parameters. What are the parameter regimes where it drops? Empirical sensitivity study: sweep body size, sweep loss rate, sweep RTT bin distribution. Yves's formula computes these cheaply; the interesting output is "at what parameter combination does$F_{\text{full}\mid C}(14)$ first drop below 0.99?". -
Adaptive body-size feedback loop. If §5.6 is used to size
bodies adaptively (lever 2 above), that creates a feedback:
smaller bodies improve
$G$ , which raises the threshold at which the producer would downsize, which allows larger bodies again. Whether that loop is stable is worth analysing before deploying.leios-testnet.md's "Cascade to livelock" section now carries the empirical measurement plan (collapse- threshold sweep, adaptive-sizing loop-gain from perturbation experiments); this open question has a concrete recipe rather than being purely analytical. - The measurement + formula combination gives a very concrete operational test. "Do we see any rounds where a certified EB fails to reach all nodes by 14 s?" is a single-line question with a single-number answer from the testnet log. If the answer is "yes, X per week", the safety property is empirically weaker than the model predicts, and CIP-0164 has to decide what to do about it (revise parameters, revise expected topology, or explicitly accept the observed failure rate).