Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — for N ≥ 2t + 1, Algorithm 1 achieves consistency, strong unanimity and termination

Proved
DLSConsensus.BasicRound.theorem_3_1

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

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

Assume the basic round model with fail-stop or omission faults, and assume N≥2t+1N\ge 2t+1N≥2t+1. Then Algorithm 1 achieves consistency, strong unanimity and termination for an arbitrary value domain.

Precisely: for every value type VVV and initial values init:{p1,…,pN}→V\mathrm{init}:\{p_1,\dots,p_N\}\to Vinit:{p1​,…,pN​}→V, every set CCC of processors with ∣C∣≥N−t|C|\ge N-t∣C∣≥N−t (the correct processors), every round GST\mathrm{GST}GST, every delivery pattern in which all messages sent between processors of CCC at rounds ≥GST\ge\mathrm{GST}≥GST are delivered (any other message may be lost), and every admissible choice of proposals, the run of Algorithm 1 satisfies

  1. consistency: any two decisions by processors in CCC are equal;
  2. strong unanimity: if all NNN initial values are vvv, every decision by a processor in CCC is vvv;
  3. termination: every processor in CCC decides.

This is the upper-bound half of the paper's result for omission and fail-stop faults with partially synchronous communication: N≥2t+1N\ge 2t+1N≥2t+1 suffices, which the paper later shows to be optimal.

Formalization Note Faulty processors are processors outside CCC that run Algorithm 1 but whose messages (sent and received) may be lost at any round; this omission model contains fail-stop. The arbitrary choice among candidates is a universally quantified admissible choice function. Runs of the basic model are infinite, so the paper's "if RRR is infinite" in the termination condition is automatic.

Preamble
import Mathlib
import Definitions.Def_DLSConsensus_BasicRound_Model
Formal statement
namespace DLSConsensus.BasicRound

/-- Theorem 3.1 (p. 297): in the basic round model with omission (in particular fail-stop)
faults, if `N ≥ 2t + 1`, Algorithm 1 achieves consistency, strong unanimity and termination
for an arbitrary value domain `V`: for every set `C` of at least `N - t` correct processors,
every round `GST`, every message-loss pattern allowed by the model, every initial values and
every admissible choice of proposals. -/
theorem theorem_3_1 {N t : ℕ} (hN : 2 * t + 1 ≤ N) {V : Type*} (init : Fin N → V)
    (C : Finset (Fin N)) (hC : N - t ≤ C.card) (GST : ℕ) (deliv : ℕ → Fin N → Fin N → Prop)
    (hdeliv : DelivOK C GST deliv) (pick : ℕ → Set V → V) (hpick : PickAdmissible pick) :
    Consistency t pick init deliv C ∧ StrongUnanimity t pick init deliv C ∧
      Termination t pick init deliv C := by sorry

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