Proof of Theorem 4.3, Scenario C — all processors alive, cross-group messages delayed past T: P acts as in Scenario A and Q as in Scenario B
ProvedDLSConsensus.LowerBound.scenario_CLet be any protocol, and fix the communication model: either holds eventually (for a positive integer ) or delta is unknown. Let be disjoint groups covering all processors, let be a run of Scenario A (all initial values , initially dead, stepping at every tick, messages delivered in time ) and a run of Scenario B (all initial values , initially dead, stepping at every tick, messages delivered in time ), and let be any time. Scenario C: there is a run allowed by the communication model such that
- all processors are alive (every processor takes a step at every tick);
- processors of have initial value and processors of have initial value ;
- messages from to and from to are delivered in time ;
- no message from to or from to is delivered at a tick ;
- for every tick , each processor of is in the same state after tick in as in , and each processor of is in the same state as in :
With this run contradicts consistency: the processors of decide and those of decide , while all processors are correct.
Formalization Note The paper says that cross-group messages "take more than steps to be delivered" and that the groups "act exactly as they do" in Scenarios A and B. The Lean states what the argument uses: no cross-group message is delivered at or before tick , and the local states agree up to tick . Taken literally, "every cross-group message takes more than steps" is not allowed when holds eventually and , because messages sent after the stabilization time must arrive within ; delaying only the deliveries up to tick is allowed in both models. is arbitrary here; the proof takes .
import Mathlib import Definitions.Def_DLSConsensus_LowerBound_Model
namespace DLSConsensus.LowerBound
/-- Scenario C of the proof of Theorem 4.3 (p. 306). Let `π` be any protocol, `cm` a communication
model (Δ holds eventually with `Δ > 0`, or delta is unknown), `P`, `Q` a partition of the processors,
`RA` a run of Scenario A (initial values `0`, `Q` initially dead, `P → P` in time 1), `RB` a run of
Scenario B (initial values `1`, `P` initially dead, `Q → Q` in time 1), and `T` any time (in the proof,
`T = max(T_A, T_B)`). Then there is a run allowed by `cm` in which all processors take a step at every
tick (all alive), processors of `P` start with `0` and those of `Q` with `1`, messages from `P` to `P`
and from `Q` to `Q` are delivered in time 1, no message between the groups is delivered at a tick
`≤ T`, and every processor of `P` (resp. `Q`) is in the same state after each tick `n ≤ T` as in `RA`
(resp. `RB`). -/
theorem scenario_C {N : ℕ} {σ M : Type} (π : Protocol N σ M) (cm : Comm) (hcm : cm.WF)
(P Q : Finset (Fin N)) (hdisj : Disjoint P Q) (hcover : P ∪ Q = Finset.univ)
(RA RB : Run N σ) (hA : IsolatedScenario π P false RA) (hB : IsolatedScenario π Q true RB)
(T : ℕ) :
∃ R : Run N σ, IsRun π R ∧ cm.Allowed π R ∧ FailStop Finset.univ R ∧
(∀ i ∈ P, R.val i = false) ∧ (∀ i ∈ Q, R.val i = true) ∧
TimeOneWithin π P R ∧ TimeOneWithin π Q R ∧
(∀ k i s n, (k, s) ∈ R.deliv i n → (k ∈ P ↔ i ∈ Q) → T < n) ∧
(∀ i ∈ P, ∀ n ≤ T, R.state i n = RA.state i n) ∧
(∀ i ∈ Q, ∀ n ≤ T, R.state i n = RB.state i n) := by sorry
end DLSConsensus.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.