Section 3 (pp. 230–231) — for n ≥ 3m + 1 the recursive procedure assures interactive consistency for m faults
ProvedInteractiveConsistency.OralAlgorithm.procedure_assures_icLet be a finite set of processors and with
Let every processor run the recursive procedure of Section 3 (steps (1)–(2), p. 230) on its own view , computing for each processor the value . Then this family assures interactive consistency for faults: for every set of nonfaulty processors with and every -level scenario consistent with ,
- for all , (each nonfaulty processor computes the private value of each nonfaulty processor);
- for all and , (all nonfaulty processors compute the same vector).
This is the positive half of the paper's characterization: interactive consistency is achievable with rounds of oral messages whenever ; the THEOREM of Section 4 shows that 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 "); the statement makes the claim explicit through AssuresICLevel. Each processor's procedure receives only its view fun w => σ (p :: w), never or . The scenario is -level: consistency with is assumed only on strings of length , which is all the procedure reads. The case (then ) is included.
import Mathlib import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario import Definitions.Def_InteractiveConsistency_OralAlgorithm_Procedure
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.