Section 4, proof (p. 233) — α, β, σ are consistent with A ∪ C, B ∪ C, A ∪ B, respectively
ProvedInteractiveConsistency.Impossibility.construction_consistentbyzantine-agreementdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , be pairwise disjoint sets with , let , and let , , be the scenarios defined by (i)–(iii) of p. 232. Then
- is consistent with ;
- is consistent with ;
- is consistent with .
That is, for instance, for all , and . Each of the three scenarios is therefore a legitimate behaviour of a system whose faulty processors are , , respectively.
Formalization Note The page asserts this "by inspection"; the statement does not need , , to be nonempty, nor , so those hypotheses of the surrounding proof are omitted.
Preamble
import Mathlib import Definitions.Def_InteractiveConsistency_Impossibility_Scenario import Definitions.Def_InteractiveConsistency_Impossibility_Construction
Formal statement
namespace InteractiveConsistency.Impossibility
/-- Pease, Shostak & Lamport (1980), Section 4, proof of the THEOREM, p. 233: for a partition
`A, B, C` of `P` and any values `v, v'`, the scenarios `α`, `β`, `σ` defined by (i)–(iii) of p. 232
are consistent with `N = A ∪ C`, `B ∪ C`, `A ∪ B`, respectively. -/
theorem construction_consistent {α V : Type*} [DecidableEq α] (P A B C : Finset α) (v v' : V)
(hAB : Disjoint A B) (hAC : Disjoint A C) (hBC : Disjoint B C) (hP : A ∪ B ∪ C = P) :
ConsistentWith P (A ∪ C) (alphaScen P A B C v v') ∧
ConsistentWith P (B ∪ C) (betaScen P A B C v v') ∧
ConsistentWith P (A ∪ B) (sigmaScen P A B C v v') := by sorry
end InteractiveConsistency.Impossibility
Source
Pease, Shostak & Lamport, Reaching agreement in the presence of faults, J. ACM 27 (1980), p. 233, Section 4, proof of the THEOREM, first sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.