Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.3 — with synchronous processors and partially synchronous communication, no t-resilient consensus for 2 ≤ N ≤ 2t fail-stop

Proved
DLSConsensus.LowerBound.theorem_4_3

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

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

Consider NNN processors with binary initial values, fail-stop faults, synchronous processors (Φ=1\Phi = 1Φ=1: every correct processor takes a step at every tick of real time), and partially synchronous communication, in either of its two forms: Δ\DeltaΔ holds eventually (for a fixed positive integer Δ\DeltaΔ known to the protocol designer, holding from some unknown global stabilization time on), or delta is unknown (some positive Δ\DeltaΔ holds from the start, but the protocol is fixed before Δ\DeltaΔ). Let ttt be an integer with 0≤t≤N0 \le t \le N0≤t≤N and assume

2≤N≤2t.2 \le N \le 2t.2≤N≤2t.

Then there is no ttt-resilient consensus protocol that achieves weak unanimity for binary values. Explicitly:

  1. for every positive integer Δ\DeltaΔ, no protocol is a ttt-resilient consensus protocol achieving weak unanimity when Δ\DeltaΔ holds eventually;
  2. no protocol is a ttt-resilient consensus protocol achieving weak unanimity when delta is unknown.

The state set and message set of the protocol are arbitrary and may be infinite.

The theorem shows that the resiliency N≥2t+1N \ge 2t + 1N≥2t+1 of the paper's protocols for fail-stop and omission faults (Theorems 4.1 and 4.2, part (a)) cannot be improved, even for weak unanimity and a binary value domain.

Formalization Note The paper states the theorem for "fail-stop or omission faults"; its proof assumes an algorithm immune to fail-stop faults. The Lean states the fail-stop impossibility, which implies the omission case: a fail-stop processor behaves, as seen by the others, like a processor whose sends are all omitted from its stop time on, so every protocol that is ttt-resilient against omission faults is ttt-resilient against fail-stop faults. The omission case is not a separate item. In part 1, Δ\DeltaΔ is chosen before the protocol, as in the paper's game reading ("the adversary picks Δ\DeltaΔ, the designer (knowing Δ\DeltaΔ) supplies a consensus protocol"); in part 2 the protocol is fixed first and the allowed runs carry their own Δ\DeltaΔ. The bound t≤Nt \le Nt≤N is the range of ttt in the paper's definition of ttt-resilience (§2.4).

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

/-- Theorem 4.3 (Dwork, Lynch, Stockmeyer 1988, p. 305), fail-stop case: with synchronous processors
(Φ = 1) and partially synchronous communication — (a) Δ holds eventually, for every positive Δ, or
(b) delta is unknown — and `2 ≤ N ≤ 2t` (with the standing `t ≤ N` of §2.4), no protocol for binary
values is a `t`-resilient consensus protocol achieving weak unanimity. The state and message types
of the protocol are arbitrary (possibly infinite). -/
theorem theorem_4_3 (N t : ℕ) (hN : 2 ≤ N) (hNt : N ≤ 2 * t) (htN : t ≤ N) :
    (∀ Δ : ℕ, 0 < Δ → ∀ (σ M : Type) (π : Protocol N σ M),
      ¬ Resilient π t (Comm.eventually Δ)) ∧
    (∀ (σ M : Type) (π : Protocol N σ M), ¬ Resilient π t Comm.unknown) := by sorry

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