Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.3, Scenario A — with Q initially dead and all inputs 0, the processors of P decide 0 within some time T_A

Proved
DLSConsensus.LowerBound.scenario_A

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

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

Let t≤Nt \le Nt≤N and let π\piπ be a ttt-resilient consensus protocol achieving weak unanimity for binary values, with fail-stop faults, synchronous processors (Φ=1\Phi = 1Φ=1), and communication in which either Δ\DeltaΔ holds eventually (for a positive integer Δ\DeltaΔ) or delta is unknown. Divide the NNN processors into two disjoint groups PPP and QQQ with P∪QP \cup QP∪Q all processors and

1≤∣P∣≤t,1≤∣Q∣≤t.1 \le |P| \le t, \qquad 1 \le |Q| \le t.1≤∣P∣≤t,1≤∣Q∣≤t.

Scenario A: all initial values are 000, the processors of QQQ are initially dead (they never take a step), the processors of PPP take a step at every tick, and every message sent from a processor of PPP to a processor of PPP is delivered in time 111. Then

  1. a run of Scenario A exists, and
  2. in every run of Scenario A there is a time TAT_ATA​ such that every processor of PPP has decided by tick TAT_ATA​, and its decision is 000.

This is the first of the three scenarios in the proof of Theorem 4.3: it fixes what the group PPP does on its own when every input is 000.

Formalization Note "Delivered in exactly time 1" is read as: delivered no later than the addressee's first Receive at a tick at least one after the send. A step is either a Send or a Receive, so a processor that sends at the next tick cannot receive then; delivery at that first Receive is the earliest delivery the model allows. "Reach a decision within time TAT_ATA​" is the explicit ∃TA\exists T_A∃TA​; "decides 0 by TAT_ATA​" means its first decision, at a tick n≤TAn \le T_An≤TA​, is 000.

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

/-- Scenario A of the proof of Theorem 4.3 (p. 305). Let `π` be a `t`-resilient consensus protocol
achieving weak unanimity in the communication model `cm` (Δ holds eventually, with `Δ > 0`, or delta
is unknown), and split the processors into two disjoint groups `P`, `Q` with `1 ≤ |P|, |Q| ≤ t`.
Scenario A — all initial values `0` (`false`), the processors of `Q` initially dead, messages from `P`
to `P` delivered in time 1 — has a run, and in every such run there is a time `T_A` by which every
processor of `P` has decided, and decided `0`. -/
theorem scenario_A {N : ℕ} {σ M : Type} (π : Protocol N σ M) (t : ℕ) (cm : Comm) (hcm : cm.WF)
    (htN : t ≤ N) (hres : Resilient π t cm) (P Q : Finset (Fin N)) (hdisj : Disjoint P Q)
    (hcover : P ∪ Q = Finset.univ) (hP1 : 1 ≤ P.card) (hPt : P.card ≤ t) (hQ1 : 1 ≤ Q.card)
    (hQt : Q.card ≤ t) :
    (∃ R : Run N σ, IsolatedScenario π P false R) ∧
    ∀ R : Run N σ, IsolatedScenario π P false R →
      ∃ TA : ℕ, ∀ i ∈ P, ∃ n ≤ TA, DecidesAt π R i false n := by sorry

end DLSConsensus.LowerBound
Source
Dwork, Lynch, Stockmeyer, Consensus in the presence of partial synchrony, J. ACM 35 (1988), pp. 305–306, proof of Theorem 4.3, Scenario A
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