Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section 3 (pp. 230–231) — for n ≥ 3m + 1 the recursive procedure assures interactive consistency for m faults

Proved
InteractiveConsistency.OralAlgorithm.procedure_assures_ic

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

byzantine-agreementdistributed-computinginteractive-consistencyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let PPP be a finite set of nnn processors and m≥0m\ge 0m≥0 with

n≥3m+1.n \ge 3m+1 .n≥3m+1.

Let every processor ppp run the recursive procedure of Section 3 (steps (1)–(2), p. 230) on its own view σp\sigma_pσp​, computing for each processor rrr the value record(m,P,σp,r)∈V∪{NIL}\mathrm{record}(m, P, \sigma_p, r)\in V\cup\{\mathrm{NIL}\}record(m,P,σp​,r)∈V∪{NIL}. Then this family assures interactive consistency for mmm faults: for every set N⊆PN\subseteq PN⊆P of nonfaulty processors with ∣N∣≥n−m|N|\ge n-m∣N∣≥n−m and every (m+1)(m+1)(m+1)-level scenario σ\sigmaσ consistent with NNN,

  1. for all p,q∈Np, q\in Np,q∈N, record(m,P,σp,q)=σ(q)\mathrm{record}(m, P, \sigma_p, q) = \sigma(q)record(m,P,σp​,q)=σ(q) (each nonfaulty processor computes the private value of each nonfaulty processor);
  2. for all p,p′∈Np, p'\in Np,p′∈N and r∈Pr\in Pr∈P, record(m,P,σp,r)=record(m,P,σp′,r)\mathrm{record}(m, P, \sigma_p, r) = \mathrm{record}(m, P, \sigma_{p'}, r)record(m,P,σp​,r)=record(m,P,σp′​,r) (all nonfaulty processors compute the same vector).

This is the positive half of the paper's characterization: interactive consistency is achievable with m+1m+1m+1 rounds of oral messages whenever n≥3m+1n\ge 3m+1n≥3m+1; the THEOREM of Section 4 shows that n≥3m+1n\ge 3m+1n≥3m+1 cannot be lowered.

Formalization Note. The paper proves this in prose ("The proof that the algorithm given above does indeed assure interactive consistency proceeds by induction on mmm"); the statement makes the claim explicit through AssuresICLevel. Each processor's procedure receives only its view fun w => σ (p :: w), never σ\sigmaσ or NNN. The scenario is (m+1)(m+1)(m+1)-level: consistency with NNN is assumed only on strings of length ≤m+2\le m+2≤m+2, which is all the procedure reads. The case m=0m = 0m=0 (then n≥1n\ge 1n≥1) is included.

Preamble
import Mathlib
import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario
import Definitions.Def_InteractiveConsistency_OralAlgorithm_Procedure
Formal statement
namespace InteractiveConsistency.OralAlgorithm

theorem procedure_assures_ic {α V : Type*} [DecidableEq α] (P : Finset α) (m : ℕ)
    (hn : 3 * m + 1 ≤ P.card) :
    AssuresICLevel (V := V) P m (fun _ => record m P) := by sorry

end InteractiveConsistency.OralAlgorithm
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), pp. 230–231, Section 3 (procedure, p. 230; proof by induction on m, p. 231); interactive consistency: p. 229 (1)–(2), p. 232 (i)–(ii)
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