Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.3, Scenario C — all processors alive, cross-group messages delayed past T: P acts as in Scenario A and Q as in Scenario B

Proved
DLSConsensus.LowerBound.scenario_C

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

consensusdistributed-computingfault-tolerancep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let π\piπ be any protocol, and fix the communication model: either Δ\DeltaΔ holds eventually (for a positive integer Δ\DeltaΔ) or delta is unknown. Let P,QP, QP,Q be disjoint groups covering all NNN processors, let RAR_ARA​ be a run of Scenario A (all initial values 000, QQQ initially dead, PPP stepping at every tick, P→PP \to PP→P messages delivered in time 111) and RBR_BRB​ a run of Scenario B (all initial values 111, PPP initially dead, QQQ stepping at every tick, Q→QQ \to QQ→Q messages delivered in time 111), and let TTT be any time. Scenario C: there is a run RRR allowed by the communication model such that

  1. all processors are alive (every processor takes a step at every tick);
  2. processors of PPP have initial value 000 and processors of QQQ have initial value 111;
  3. messages from PPP to PPP and from QQQ to QQQ are delivered in time 111;
  4. no message from PPP to QQQ or from QQQ to PPP is delivered at a tick ≤T\le T≤T;
  5. for every tick n≤Tn \le Tn≤T, each processor of PPP is in the same state after tick nnn in RRR as in RAR_ARA​, and each processor of QQQ is in the same state as in RBR_BRB​:
stateiR(n)=stateiRA(n) (i∈P),stateiR(n)=stateiRB(n) (i∈Q),n≤T.\mathrm{state}^R_i(n) = \mathrm{state}^{R_A}_i(n)\ (i \in P), \qquad \mathrm{state}^R_i(n) = \mathrm{state}^{R_B}_i(n)\ (i \in Q), \qquad n \le T.stateiR​(n)=stateiRA​​(n) (i∈P),stateiR​(n)=stateiRB​​(n) (i∈Q),n≤T.

With T=max⁡(TA,TB)T = \max(T_A, T_B)T=max(TA​,TB​) this run contradicts consistency: the processors of PPP decide 000 and those of QQQ decide 111, while all processors are correct.

Formalization Note The paper says that cross-group messages "take more than max⁡(TA,TB)\max(T_A, T_B)max(TA​,TB​) steps to be delivered" and that the groups "act exactly as they do" in Scenarios A and B. The Lean states what the argument uses: no cross-group message is delivered at or before tick TTT, and the local states agree up to tick TTT. Taken literally, "every cross-group message takes more than TTT steps" is not allowed when Δ\DeltaΔ holds eventually and Δ≤T\Delta \le TΔ≤T, because messages sent after the stabilization time must arrive within Δ\DeltaΔ; delaying only the deliveries up to tick TTT is allowed in both models. TTT is arbitrary here; the proof takes T=max⁡(TA,TB)T = \max(T_A, T_B)T=max(TA​,TB​).

Preamble
import Mathlib
import Definitions.Def_DLSConsensus_LowerBound_Model
Formal statement
namespace DLSConsensus.LowerBound

/-- Scenario C of the proof of Theorem 4.3 (p. 306). Let `π` be any protocol, `cm` a communication
model (Δ holds eventually with `Δ > 0`, or delta is unknown), `P`, `Q` a partition of the processors,
`RA` a run of Scenario A (initial values `0`, `Q` initially dead, `P → P` in time 1), `RB` a run of
Scenario B (initial values `1`, `P` initially dead, `Q → Q` in time 1), and `T` any time (in the proof,
`T = max(T_A, T_B)`). Then there is a run allowed by `cm` in which all processors take a step at every
tick (all alive), processors of `P` start with `0` and those of `Q` with `1`, messages from `P` to `P`
and from `Q` to `Q` are delivered in time 1, no message between the groups is delivered at a tick
`≤ T`, and every processor of `P` (resp. `Q`) is in the same state after each tick `n ≤ T` as in `RA`
(resp. `RB`). -/
theorem scenario_C {N : ℕ} {σ M : Type} (π : Protocol N σ M) (cm : Comm) (hcm : cm.WF)
    (P Q : Finset (Fin N)) (hdisj : Disjoint P Q) (hcover : P ∪ Q = Finset.univ)
    (RA RB : Run N σ) (hA : IsolatedScenario π P false RA) (hB : IsolatedScenario π Q true RB)
    (T : ℕ) :
    ∃ R : Run N σ, IsRun π R ∧ cm.Allowed π R ∧ FailStop Finset.univ R ∧
      (∀ i ∈ P, R.val i = false) ∧ (∀ i ∈ Q, R.val i = true) ∧
      TimeOneWithin π P R ∧ TimeOneWithin π Q R ∧
      (∀ k i s n, (k, s) ∈ R.deliv i n → (k ∈ P ↔ i ∈ Q) → T < n) ∧
      (∀ i ∈ P, ∀ n ≤ T, R.state i n = RA.state i n) ∧
      (∀ i ∈ Q, ∀ n ≤ T, R.state i n = RB.state i n) := by sorry

end DLSConsensus.LowerBound
Source
Dwork, Lynch, Stockmeyer, Consensus in the presence of partial synchrony, J. ACM 35 (1988), p. 306, proof of Theorem 4.3, Scenario C
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me