THEOREM (Section 4) — for |V| ≥ 2 and 3 ≤ n ≤ 3m no {F_p} assures interactive consistency for m faults
ProvedInteractiveConsistency.Impossibility.no_interactive_consistency_of_le_three_mulLet be a finite set of processors, a set of values and a natural number. Suppose that has at least two elements and that
Then there is no family of decision functions, each taking the -scenario and a processor to a value , that assures interactive consistency for faults.
In words: when a third or more of the processors may be faulty, no protocol — however many rounds of message exchange it uses — lets every nonfaulty processor compute the true private value of every nonfaulty processor and lets all nonfaulty processors agree on the whole vector. Together with the algorithm of Section 3 for , it shows that is exactly the condition for interactive consistency with oral (unauthenticated) messages.
Formalization Note The paper prints the hypothesis as "". This is a misprint: the proof begins "Since ", the section is titled "Proof of Impossibility for ", and with the statement is false (Section 3 solves , ). The hypothesis , used in the proof to split into three nonempty sets, is made explicit; without it the statement is false (for , assures interactive consistency). is written as the existence of two distinct values. Decision functions see only ; scenarios are defined on strings of every length.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_InteractiveConsistency_Impossibility_Scenario
namespace InteractiveConsistency.Impossibility
/-- Pease, Shostak & Lamport (1980), Section 4, THEOREM, p. 232 (with the printed hypothesis
`n ≥ 3m` corrected to `n ≤ 3m`, as the proof and the section title require, and with the implicit
`n ≥ 3` of the proof made explicit): if `|V| ≥ 2` and `3 ≤ n ≤ 3m`, where `n = |P|`, there exists no
family `{F_p | p ∈ P}` that assures interactive consistency for `m` faults. -/
theorem no_interactive_consistency_of_le_three_mul {α V : Type*} [DecidableEq α]
(P : Finset α) (m : ℕ) (hV : ∃ v v' : V, v ≠ v')
(h3 : 3 ≤ P.card) (hn : P.card ≤ 3 * m) :
∀ F : α → (List α → V) → α → V, ¬ AssuresIC P m F := by sorry
end InteractiveConsistency.Impossibility
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.