Section 5 — a faulty originator's reports transfer between nonfaulty receivers
ProvedInteractiveConsistency.Authenticated.faulty_origin_set_subsetauthenticated-messagesbyzantine-agreementdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set of processors with , and let satisfy . Let be an authenticated -level scenario consistent with , with non-NIL private values. If are nonfaulty and is faulty, then
The inclusion is valid for every ordered pair of nonfaulty receivers. Applying it with their roles exchanged gives equality of the two sets, which supplies agreement for a faulty originator.
Formalization Note Each set uses only its named receiver's own view. The bound on the number of faulty processors includes , and the relay strings have distinct letters, avoid the receiver and originator, and have length at most .
Preamble
import Mathlib import Definitions.Def_InteractiveConsistency_Authenticated_Procedure set_option autoImplicit false
Formal statement
namespace InteractiveConsistency.Authenticated
/-- Section 5, p. 234: for a faulty originator, every non-NIL report seen by
one nonfaulty receiver is also seen by every other nonfaulty receiver. -/
theorem faulty_origin_set_subset {α V : Type*} [DecidableEq α]
(P N : Finset α) (m : ℕ) (σ : List α → Option V)
(hmn : m ≤ P.card) (hN : N ⊆ P) (hcount : P.card ≤ N.card + m)
(hscenario : IsAuthScenario P σ)
(hconsistent : AuthConsistent P N m σ)
(p p' q : α) (hp : p ∈ N) (hp' : p' ∈ N)
(hqP : q ∈ P) (hqN : q ∉ N) :
S m P (view σ p) p q ⊆ S m P (view σ p') p' q := by sorry
end InteractiveConsistency.Authenticated
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), p. 234, Section 5 proof paragraph; https://doi.org/10.1145/322186.322188
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.