Section 3, note after step (2) (p. 230) — σ̂(w) = σ(wq) is an m-level scenario on P − {q} consistent with N
ProvedInteractiveConsistency.OralAlgorithm.subscenario_consistentLet be a finite set of processors, , with , and an -level scenario consistent with . Let be faulty, . Define
for strings over . Then , , and is an -level scenario on consistent with .
The paper notes that "corresponds to the -level subscenario of in which is excluded and in which each processor's private value is the value it obtains directly from in ", and its induction hypothesis is applied to this subscenario. The restriction of to strings beginning with is exactly the view that the recursive call of step (2) receives.
Formalization Note. is fun w => σ (w ++ [q]); level means consistency on strings of length (ConsistentUpTo (P.erase q) N (m' + 1)). is written (P.erase q).card ≤ N.card + m'.
import Mathlib import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario
namespace InteractiveConsistency.OralAlgorithm
theorem subscenario_consistent {α V : Type*} [DecidableEq α] (P N : Finset α) (m' : ℕ)
(hNP : N ⊆ P) (hN : P.card ≤ N.card + (m' + 1))
(σ : List α → V) (hσ : ConsistentUpTo P N (m' + 2) σ)
(q : α) (hqP : q ∈ P) (hqN : q ∉ N) :
N ⊆ P.erase q ∧ (P.erase q).card ≤ N.card + m' ∧
ConsistentUpTo (P.erase q) N (m' + 1) (fun w => σ (w ++ [q])) := by sorry
end InteractiveConsistency.OralAlgorithm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.