Section 3, Induction Step ¶3 (p. 231) — two step-(1) quorums give the same value
ProvedInteractiveConsistency.OralAlgorithm.step_one_values_agreebyzantine-agreementdistributed-computinginteractive-consistencyp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set of processors, with , and an -level scenario consistent with . Let be nonfaulty and . Suppose both have more than members, and satisfy
Then .
This is the case of the paper's proof in which both and exit the procedure at step (1): the two quorums share more than members, one of them nonfaulty, so both quorums yield the same value.
Formalization Note. is σ (p :: (w ++ [q])), i.e. . "More than members" is P.card + m < 2 * Qᵢ.card. The hypothesis of Section 3 is not needed for this step and is omitted, which makes the statement stronger.
Preamble
import Mathlib import Definitions.Def_InteractiveConsistency_OralAlgorithm_Scenario
Formal statement
namespace InteractiveConsistency.OralAlgorithm
theorem step_one_values_agree {α V : Type*} [DecidableEq α] (P N : Finset α) (m : ℕ)
(hNP : N ⊆ P) (hN : P.card ≤ N.card + m)
(σ : List α → V) (hσ : ConsistentUpTo P N (m + 1) σ)
(p p' q : α) (hp : p ∈ N) (hp' : p' ∈ N) (hq : q ∈ P)
(Q₁ Q₂ : Finset α) (hQ₁ : Q₁ ⊆ P) (hQ₂ : Q₂ ⊆ P)
(hQ₁card : P.card + m < 2 * Q₁.card) (hQ₂card : P.card + m < 2 * Q₂.card)
(v v' : V)
(hv : ∀ w : List α, IsStringOver Q₁ w → w.length ≤ m → σ (p :: (w ++ [q])) = v)
(hv' : ∀ w : List α, IsStringOver Q₂ w → w.length ≤ m → σ (p' :: (w ++ [q])) = v') :
v = v' := by sorry
end InteractiveConsistency.OralAlgorithm
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), p. 231, Section 3, Induction Step ¶3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.