Proof of Theorem 4.3, Scenario A — with Q initially dead and all inputs 0, the processors of P decide 0 within some time T_A
ProvedDLSConsensus.LowerBound.scenario_ALet 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 A: all initial values are , the processors of are initially dead (they never take a step), 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 A exists, and
- in every run of Scenario A there is a time such that every processor of has decided by tick , and its decision is .
This is the first of the three scenarios in the proof of Theorem 4.3: it fixes what the group does on its own when every input is .
Formalization Note "Delivered in exactly time 1" is read as: delivered no later than the addressee's first Receive at a tick at least one after the send. A step is either a Send or a Receive, so a processor that sends at the next tick cannot receive then; delivery at that first Receive is the earliest delivery the model allows. "Reach a decision within time " is the explicit ; "decides 0 by " means its first decision, at a tick , is .
import Mathlib import Definitions.Def_DLSConsensus_LowerBound_Model
namespace DLSConsensus.LowerBound
/-- Scenario A of the proof of Theorem 4.3 (p. 305). Let `π` be a `t`-resilient consensus protocol
achieving weak unanimity in the communication model `cm` (Δ holds eventually, with `Δ > 0`, or delta
is unknown), and split the processors into two disjoint groups `P`, `Q` with `1 ≤ |P|, |Q| ≤ t`.
Scenario A — all initial values `0` (`false`), the processors of `Q` initially dead, messages from `P`
to `P` delivered in time 1 — has a run, and in every such run there is a time `T_A` by which every
processor of `P` has decided, and decided `0`. -/
theorem scenario_A {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 π P false R) ∧
∀ R : Run N σ, IsolatedScenario π P false R →
∃ TA : ℕ, ∀ i ∈ P, ∃ n ≤ TA, DecidesAt π R i false n := by sorry
end DLSConsensus.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.