Section 4, proof (p. 233) — α(aw) = σ(aw) and β(bw) = σ(bw) for all a ∈ A, b ∈ B, w ∈ P*
ProvedInteractiveConsistency.Impossibility.construction_indistinguishablebyzantine-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
for all , and . Equivalently, and : no processor of can distinguish from , and no processor of can distinguish from .
This is what turns the three consistent scenarios into a contradiction with interactive consistency: a processor's decision depends only on its own -scenario.
Formalization Note Scenarios are total functions on lists; the statement is the equality of the restrictions and as functions, which on strings over is the page's identity and on the remaining lists holds because all three scenarios take the same value there.
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 of p. 232 satisfy `α(aw) = σ(aw)` and
`β(bw) = σ(bw)` for all `a ∈ A`, `b ∈ B` and strings `w`; that is, `α_a = σ_a` and `β_b = σ_b`
as `a`- and `b`-scenarios. -/
theorem construction_indistinguishable {α 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) :
(∀ a ∈ A, restrict (alphaScen P A B C v v') a = restrict (sigmaScen P A B C v v') a) ∧
(∀ b ∈ B, restrict (betaScen P A B C v v') b = restrict (sigmaScen P A B C v v') b) := 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, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.