Theorem 2 — linear stabilisation lower bound for pulse synchronisation
ProvedPulseSyncLowerBound.Pulse.theorem_2Let , let satisfy , and suppose . Every deterministic finite-state -resilient pulse synchronisation protocol of skew that stabilises in rounds must satisfy the strict bound
The quantification includes all finite nonempty local state spaces, every full initial configuration, and every infinite synchronous execution with at most total crashes. Stabilisation means the first pulse interval starts by , each non-faulty process pulses exactly once in each interval of width at most , and consecutive intervals are separated by more than with no intervening pulses. There is no upper frequency bound, and no assumption .
This is an operational impossibility with the source's exact constant, including the small- cases where its subtracted threshold is negative.
Differences from the source:
- encoding: processes numbered 1 through n with pairwise disjoint finite local state sets (operationally nonempty) → Fin n identities and arbitrary finite nonempty dependent local state types, with identity-tagged states and views; reason: zero-based relabelling and tagged disjoint union preserve every process, state, and execution; nonemptiness is the operational state convention used explicitly in the Lemma 12 proof
- reading: Theorem 2 writes sigma>0 without declaring its type, while Definition 1 requires sigma≥1 → use Definition 1’s stated domain sigma≥1; reason: the task is not defined by the source below one; positive integer skews are all included
- generalization: the reduction uses the integer modulus q=2sigma+1 → the goal admits every finite real skew sigma≥1; reason: integer interval endpoints give exactly the same pulse predicate at s=floor(sigma); the integer-skew bound T+2s>floor(f/2) implies T+2sigma>floor(f/2)
- encoding: no protocol stabilises in floor(f/2)−2sigma rounds → for every natural stabilisation bound T, T+2sigma>floor(f/2) in the reals; reason: the additive strict inequality preserves negative thresholds and monotonicity in the allowed stabilisation time, without truncated natural subtraction
import Definitions.Def_PulseSyncLowerBound_Pulse_Tasks
namespace PulseSyncLowerBound.Pulse
attribute [local instance] Classical.propDecidable Classical.decEq
theorem theorem_2 {n f T : ℕ} (σ : ℝ) (P : Protocol n Bool)
(hσ : 1 ≤ σ) (hn : f + 2 < n) (hP : PulseResilient P f σ T) :
((f / 2 : ℕ) : ℝ) < (T : ℝ) + 2 * σ := by sorry
end PulseSyncLowerBound.Pulse
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.