Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.3, Scenario B — with P initially dead and all inputs 1, the processors of Q decide 1 within some time T_B

Proved
DLSConsensus.LowerBound.scenario_B

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 B: all initial values are 111, the processors of PPP are initially dead, the processors of QQQ take a step at every tick, and every message sent from a processor of QQQ to a processor of QQQ is delivered in time 111. Then

  1. a run of Scenario B exists, and
  2. in every run of Scenario B there is a finite time TBT_BTB​ such that every processor of QQQ has decided by tick TBT_BTB​, and its decision is 111.

This is the mirror image of Scenario A, with the roles of PPP and QQQ and of the values 000 and 111 exchanged.

Formalization Note "Delivered in exactly time 1" is read as in Scenario A: no later than the addressee's first Receive at least one tick after the send. "Within TBT_BTB​ steps for some finite TBT_BTB​" is the explicit ∃TB\exists T_B∃TB​.

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

/-- Scenario B of the proof of Theorem 4.3 (p. 306), symmetric to Scenario A. Let `π` be a
`t`-resilient consensus protocol achieving weak unanimity in the communication model `cm`, and split
the processors into two disjoint groups `P`, `Q` with `1 ≤ |P|, |Q| ≤ t`. Scenario B — all initial
values `1` (`true`), the processors of `P` initially dead, messages from `Q` to `Q` delivered in
time 1 — has a run, and in every such run there is a finite `T_B` by which every processor of `Q` has
decided, and decided `1`. -/
theorem scenario_B {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 π Q true R) ∧
    ∀ R : Run N σ, IsolatedScenario π Q true R →
      ∃ TB : ℕ, ∀ i ∈ Q, ∃ n ≤ TB, DecidesAt π R i true 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 B
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