Theorem 4.3 — with synchronous processors and partially synchronous communication, no t-resilient consensus for 2 ≤ N ≤ 2t fail-stop
ProvedDLSConsensus.LowerBound.theorem_4_3Consider processors with binary initial values, fail-stop faults, synchronous processors (: every correct processor takes a step at every tick of real time), and partially synchronous communication, in either of its two forms: holds eventually (for a fixed positive integer known to the protocol designer, holding from some unknown global stabilization time on), or delta is unknown (some positive holds from the start, but the protocol is fixed before ). Let be an integer with and assume
Then there is no -resilient consensus protocol that achieves weak unanimity for binary values. Explicitly:
- for every positive integer , no protocol is a -resilient consensus protocol achieving weak unanimity when holds eventually;
- no protocol is a -resilient consensus protocol achieving weak unanimity when delta is unknown.
The state set and message set of the protocol are arbitrary and may be infinite.
The theorem shows that the resiliency of the paper's protocols for fail-stop and omission faults (Theorems 4.1 and 4.2, part (a)) cannot be improved, even for weak unanimity and a binary value domain.
Formalization Note The paper states the theorem for "fail-stop or omission faults"; its proof assumes an algorithm immune to fail-stop faults. The Lean states the fail-stop impossibility, which implies the omission case: a fail-stop processor behaves, as seen by the others, like a processor whose sends are all omitted from its stop time on, so every protocol that is -resilient against omission faults is -resilient against fail-stop faults. The omission case is not a separate item. In part 1, is chosen before the protocol, as in the paper's game reading ("the adversary picks , the designer (knowing ) supplies a consensus protocol"); in part 2 the protocol is fixed first and the allowed runs carry their own . The bound is the range of in the paper's definition of -resilience (§2.4).
import Mathlib import Definitions.Def_DLSConsensus_LowerBound_Model
namespace DLSConsensus.LowerBound
/-- Theorem 4.3 (Dwork, Lynch, Stockmeyer 1988, p. 305), fail-stop case: with synchronous processors
(Φ = 1) and partially synchronous communication — (a) Δ holds eventually, for every positive Δ, or
(b) delta is unknown — and `2 ≤ N ≤ 2t` (with the standing `t ≤ N` of §2.4), no protocol for binary
values is a `t`-resilient consensus protocol achieving weak unanimity. The state and message types
of the protocol are arbitrary (possibly infinite). -/
theorem theorem_4_3 (N t : ℕ) (hN : 2 ≤ N) (hNt : N ≤ 2 * t) (htN : t ≤ N) :
(∀ Δ : ℕ, 0 < Δ → ∀ (σ M : Type) (π : Protocol N σ M),
¬ Resilient π t (Comm.eventually Δ)) ∧
(∀ (σ M : Type) (π : Protocol N σ M), ¬ Resilient π t Comm.unknown) := by sorry
end DLSConsensus.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.