Section 3.2.1, p. 298 — all correct processors decide by round GST + 4(N + 1)
ProvedDLSConsensus.BasicRound.decision_round_boundconsensusdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Assume the basic round model with omission (in particular fail-stop) faults and . Let be any set of at least processors, any round, any delivery pattern allowed for and , any initial values in an arbitrary domain , and any admissible choice function. Then every processor decides some value at some phase whose decision round satisfies
This is the quantitative form of termination for Algorithm 1: decisions come at most a constant number of phases (linear in ) after GST.
Formalization Note The paper's "make decisions by round GST + 4(N+1)" is read as: the decision event (the computation subround of round of the deciding phase ) happens at a round at most .
Preamble
import Mathlib import Definitions.Def_DLSConsensus_BasicRound_Model
Formal statement
namespace DLSConsensus.BasicRound
/-- Section 3.2.1, p. 298: under the hypotheses of Theorem 3.1, every processor in `C` decides at
some phase `k` whose decision round `4k - 1` is at most `GST + 4(N + 1)`. -/
theorem decision_round_bound {N t : ℕ} (hN : 2 * t + 1 ≤ N) {V : Type*} (init : Fin N → V)
(C : Finset (Fin N)) (hC : N - t ≤ C.card) (GST : ℕ) (deliv : ℕ → Fin N → Fin N → Prop)
(hdeliv : DelivOK C GST deliv) (pick : ℕ → Set V → V) (hpick : PickAdmissible pick) :
∀ p ∈ C, ∃ (k : ℕ) (v : V),
DecidesAt t pick init deliv p k v ∧ 4 * k - 1 ≤ GST + 4 * (N + 1) := by sorry
end DLSConsensus.BasicRound
Source
Dwork, Lynch, Stockmeyer, Consensus in the presence of partial synchrony, J. ACM 35 (1988), p. 298, Section 3.2.1 (sentence after the proof of Theorem 3.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.