Section 3, Induction Step ¶1 (p. 231) — for nonfaulty p, q, step (1) succeeds and p records σ(q)
ProvedInteractiveConsistency.OralAlgorithm.record_of_nonfaultyLet be a finite set of processors, with , a set of nonfaulty processors with , and an -level scenario consistent with . For all nonfaulty , the condition of step (1) of the Section 3 procedure holds for 's view and the processor , and
This is clause (i) of interactive consistency. The paper argues it at the start of the induction step: the set of nonfaulty processors has members and every relay chain through it reproduces , so it qualifies as in step (1).
Formalization Note. The paper writes this inside the induction step () and the basis separately; the statement covers every . The paper's "p records and " is a printed slip for "records for ". The view of is fun w => σ (p :: w) and the recorded value is some (σ [q]).
import Mathlib import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario import Definitions.Def_InteractiveConsistency_OralAlgorithm_Procedure
namespace InteractiveConsistency.OralAlgorithm
theorem record_of_nonfaulty {α V : Type*} [DecidableEq α] (P N : Finset α) (m : ℕ)
(hn : 3 * m + 1 ≤ P.card) (hNP : N ⊆ P) (hN : P.card ≤ N.card + m)
(σ : List α → V) (hσ : ConsistentUpTo P N (m + 1) σ)
(p q : α) (hp : p ∈ N) (hq : q ∈ N) :
StepOne m P (fun w => σ (p :: w)) q ∧
record m P (fun w => σ (p :: w)) q = some (σ [q]) := by sorry
end InteractiveConsistency.OralAlgorithm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.