Proof of Theorem 4.3, Scenario B — with P initially dead and all inputs 1, the processors of Q decide 1 within some time T_B
ProvedDLSConsensus.LowerBound.scenario_BLet and let be a -resilient consensus protocol achieving weak unanimity for binary values, with fail-stop faults, synchronous processors (), and communication in which either holds eventually (for a positive integer ) or delta is unknown. Divide the processors into two disjoint groups and with all processors and
Scenario B: all initial values are , the processors of are initially dead, the processors of take a step at every tick, and every message sent from a processor of to a processor of is delivered in time . Then
- a run of Scenario B exists, and
- in every run of Scenario B there is a finite time such that every processor of has decided by tick , and its decision is .
This is the mirror image of Scenario A, with the roles of and and of the values and exchanged.
Formalization Note "Delivered in exactly time 1" is read as in Scenario A: no later than the addressee's first Receive at least one tick after the send. "Within steps for some finite " is the explicit .
import Mathlib import Definitions.Def_DLSConsensus_LowerBound_Model
namespace DLSConsensus.LowerBound
/-- Scenario B of the proof of Theorem 4.3 (p. 306), symmetric to Scenario A. Let `π` be a
`t`-resilient consensus protocol achieving weak unanimity in the communication model `cm`, and split
the processors into two disjoint groups `P`, `Q` with `1 ≤ |P|, |Q| ≤ t`. Scenario B — all initial
values `1` (`true`), the processors of `P` initially dead, messages from `Q` to `Q` delivered in
time 1 — has a run, and in every such run there is a finite `T_B` by which every processor of `Q` has
decided, and decided `1`. -/
theorem scenario_B {N : ℕ} {σ M : Type} (π : Protocol N σ M) (t : ℕ) (cm : Comm) (hcm : cm.WF)
(htN : t ≤ N) (hres : Resilient π t cm) (P Q : Finset (Fin N)) (hdisj : Disjoint P Q)
(hcover : P ∪ Q = Finset.univ) (hP1 : 1 ≤ P.card) (hPt : P.card ≤ t) (hQ1 : 1 ≤ Q.card)
(hQt : Q.card ≤ t) :
(∃ R : Run N σ, IsolatedScenario π Q true R) ∧
∀ R : Run N σ, IsolatedScenario π Q true R →
∃ TB : ℕ, ∀ i ∈ Q, ∃ n ≤ TB, DecidesAt π R i true n := by sorry
end DLSConsensus.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.