leios conditional diffusion

Yves Hauser's §5.6 — supporting the full-diffusion conditional analysis

Purpose

Yves Hauser's extension to the Leios ΔQ report (branch yveshauser/improved-deltaq-notebook in ouroboros-leios; files 5.6-full-diffusion-framing-draft.md and 5.6-conditional-derivation-walkthrough.md) adds a §5.6 that 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}$?

Why it matters. Linear Leios inherits from Full Leios (Coretti et al. 2025, Lemma 7) 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.

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.

What §5.6 computes

The closed-form result:

$$F_{\text{full}\mid C}(t) = \frac{G(t)^N \cdot \overline{B}(\lceil\tau M\rceil-1;, M,, G(t_v)/G(t))}{P(C)}\quad(t \ge t_v)$$

In plain English. The numerator is the joint probability that all $N$ nodes arrived by $t$ and the voter subset generated a quorum by $t_v$. The denominator is the marginal certification probability $P(C)$. Their ratio is Bayes' rule turning the joint into the conditional "given certification, everyone made it".

Where:

• $G(t)$ = the per-node EB-body arrival CDF from multi-hop diffusion. This is cdf_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.

Headline result at the report's default parameters: $F_{\text{full}\mid C}(14) \approx 1.000$ at every EB body size up to 512 kB, under either Mathis or CUBIC. The formula's interesting structure (the Binomial factor) only becomes informative when $G(t)$ is appreciably below 1 in $[t_v, t]$, which is not the case at those parameters.

Modelling assumptions. Yves's derivation lists six explicit caveats:

1. 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.
2. Committee size fixed at $M = 600$ — real Leios uses stake-weighted Poisson sortition. The bias largely cancels in the numerator/denominator ratio.
3. $G$ scope is EB body only — the 12 MB closure needs a different formulation (§5.7 covers that separately).
4. 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.
5. Comparison to Coretti et al. 2025 Lemma 7 is by analogy — the formula is a fresh ΔQ-model derivation.
6. No Monte Carlo cross-validation in Yves's version.

Which caveats our machinery addresses. Caveats 1, 3, 4, and 6 are addressable by measurement — 1 and 4 via the per-EB arrival log (see below), 3 by extending the framing to closure fetch (per §5.7 in Yves's plan; also touches our tx-submission machinery), and 6 by the empirical validation recipe in this document. 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.

Supporting the analytical assessment

Our tracing produces empirical replacements for the formula's inputs.

Per-hop CDF from estBurstS

Every response burst on the testnet gives one per-hop throughput sample (bytes-per-second on that hop under the actual congestion regime, actual $p$, actual buffering). Aggregated across many samples per peer-distance bin, this yields an empirical per-hop transfer-time CDF directly comparable to the report's analytical Mathis/CUBIC CDF. Substituting the empirical per-hop CDF into the convolution that produces $G$ yields an empirically-grounded $G$ that plugs directly into Yves's formula.

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.

Path-length distribution

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-mainnet and analysis notebook cfd.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 $G$'s convolution.

i.i.d.-vs-correlated check (Yves's caveat 1)

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.

Stake-independent hop count check (Yves's caveat 4)

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.

Validating $F_{\text{full}\mid C}$ empirically

The formula's output is directly measurable — we don't have to validate only the inputs. Recipe:

1. 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.
2. Certification outcome per EB. From cardano-tracer's block-diffusion / EB-certification traces.
3. 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}$.
4. Empirical estimator.

$$\hat{F}_{\text{full}\mid C}(14) = \frac{#{j : C_j \text{ AND all arrived by 14 s}}}{#{j : C_j}}$$

5. 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.

Tail power caveat

At $F_{\text{full}\mid C}(14) \approx 1.000$, we're measuring very rare events. Distinguishing:

• 1.000 from 0.999 requires ~1000+ EBs.
• 0.999 from 0.99 requires ~100+ EBs.
• 0.99 from 0.9 requires ~10+ EBs.

A week of testnet at 1 EB per 20 s gives ~30 k EBs — plenty for p95-scale distinctions, borderline for p99.9. If the formula predicts 1.000 but reality is 0.98, ~50 counter-examples per week are observable. Detection of failures on that scale is feasible.

Derived validations from the same data

• 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 (see leios-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 (see leios-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.

Adaptive levers for improving $F_{\text{full}\mid C}$

The formula makes clear what "improving the odds" means: $G(t)$'s tail is what matters, and specifically the dependence on the slowest nodes via $G(t)^N$. Levers ordered by leverage:

1. Slowest-node targeting

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 $\arg\max_i T_j^{(i)}$ across EBs falls into one of three regimes (persistent / rotating / bimodal), and this lever pays off only in the first:

• 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.

2. Adaptive body sizing at production time

Yves's formula gives the quantitative justification for how much improvement each 100 kB shave off the EB body buys, via its dependence on $G$ (which depends on body size).

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 $S_{EB\text{-}tx}$ sizing" lever from 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.

3. Voter self-throttle (indirect improver)

This lever is structurally different from 1, 2, 4, 5: it does not improve $F_{\text{full}\mid C}$ directly. It reshapes $P(C)$ (the marginal certification probability) by removing the slowest voters from the tally; certified rounds then have systematically better voter-arrival distributions than they otherwise would. Under positive cross-node correlation of $T_i$ (which is Yves's caveat 1 and likely the real-world case), that improvement in voter timing correlates with improvement in non-voter timing, so $F_{\text{full}\mid C}$ is higher on the rounds that certify — but the base rate is unchanged.

Trigger: a voter observing its own EB arrival approaching $t_v = 7,\text{s}$ can refuse to vote for that round.

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.

4. Freshest-First-Delivery driven by observed $T_j$

A non-voter node close to $t = 14,\text{s}$ that hasn't yet received the EB body can actively pull it from a peer (rather than waiting on its default upstream diffusion). This turns a passive receive into an active pull for the tail of $G$, empirically improving $G(14)$ on rounds where it would otherwise miss.

Trigger: the node observing its own time budget approaching 14 s without the body in hand. In practice the peer-to-ask is knowable — the peer that announced the current EB's header earliest (via the Leios notify protocol) is a natural candidate, since header propagation typically precedes body propagation. That converts the FFD trigger from "coordination signal" into "an active blockfetch pull directed at the header-first peer".

5. Peer-topology-aware peer selection

The path-length distribution feeding $G$ is shaped by peer selection. Options:

• 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 $G$. The current network stack's peer-selection strategy is a mix; the formula plus measurement can quantify the trade-off.

Connection to existing report-gaps

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.

Follow-up ideas / open questions

• MC cross-validation of §5.6. Yves's caveat 6 notes no MC validation. Given the empirical measurement recipe above produces an $\hat{F}_{\text{full}\mid C}(14)$ directly, MC becomes redundant if the testnet is running. If it isn't, an MC simulator (as in the mainline §5.6's single-node MC) extended to N-node correlated arrivals would fill the gap.
• Closure-coverage analogue (§5.7 in Yves's framing). The §5.6 formula is body-only. A "did the EB closure reach all nodes" formulation needs a different structure (closure-fetch is conditional cache-miss, not uniform diffusion). Interesting to see whether our tracing supports that formulation too — the per-mini-protocol DeltaQ on tx-submission is directly relevant, since closure fetch is via tx-submission.
• 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).