Section 5 — a nonfaulty originator yields a singleton S_pq
ProvedInteractiveConsistency.Authenticated.nonfaulty_origin_setauthenticated-messagesbyzantine-agreementdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set of processors, the nonfaulty set, and an upper bound on the number of faults, so that . Let be an authenticated -level scenario consistent with , with non-NIL private values. For nonfaulty processors , the originator has a private value and
This identifies the set from which receiver makes its decision when the originator is nonfaulty, including the case .
Formalization Note The set is computed from 's view , with intermediate strings of distinct processors of length at most . The theorem makes the paper's actual private value explicit by asserting , rather than treating NIL as a possible private value.
Preamble
import Mathlib import Definitions.Def_InteractiveConsistency_Authenticated_Procedure set_option autoImplicit false
Formal statement
namespace InteractiveConsistency.Authenticated
/-- Section 5, p. 233: a nonfaulty originator's value is the sole non-NIL
value visible in the receiver's set. -/
theorem nonfaulty_origin_set {α 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 q : α) (hp : p ∈ N) (hq : q ∈ N) :
∃ v : V, σ [q] = some v ∧ S m P (view σ p) p q = {v} := by sorry
end InteractiveConsistency.Authenticated
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), p. 233, Section 5 final paragraph; https://doi.org/10.1145/322186.322188
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.