Theorem 10 — exact non-trivial counting needs more than f rounds
OpenPulseSyncLowerBound.Pulse.Supplement.theorem_10Let with , and . There is no deterministic finite-state protocol for -resilient exact non-trivial -counting, i.e. non-trivial -approximate -counting with skew (Definitions 4 and 5), that stabilises in
Here the protocol must satisfy:
- (N1) every execution with at most crashes, from any initial configuration, has a -lift of the outputs from round onwards: integer values with , for all non-faulty , and , for all ;
- (N2) in some crash-free execution, the output of some process changes infinitely often.
The theorem says these two requirements are incompatible after only rounds. Compared with the general lower bound (Theorem 6), the skew is , the excluded stabilisation time is rather than , and the resilience requirement is the weaker .
Formalization Note The statement uses the published base predicate CountingResilient P f 0 f (Definitions 4 and 5) over the published base protocol model; a protocol stabilising in fewer rounds also satisfies the predicate at , so smaller stabilisation times are excluded too.
Differences from the source:
- encoding: processes numbered 1 through n with finite local state sets → Fin n identities and arbitrary finite nonempty dependent local state types (the published base model); reason: zero-based relabelling preserves every process, state and execution; finiteness is the paper's model (§2) and nonemptiness its operational state convention
- encoding: outputs in Z_q and a 0-lift on non-faulty processes times Z → Fin q outputs and integer lifts on all identities at natural times, constrained only on non-faulty identities and t ≥ f; reason: Fin q is the residue set; unconstrained identities and negative times extend arbitrarily, so every L1–L3 instance is preserved
import Definitions.Def_PulseSyncLowerBound_Pulse_Tasks
namespace PulseSyncLowerBound.Pulse.Supplement
open PulseSyncLowerBound.Pulse
attribute [local instance] Classical.propDecidable Classical.decEq
theorem theorem_10 {n q f : ℕ} (P : Protocol n (Fin q))
(hq : 2 ≤ q) (hf : 0 < f) (hn : f + 1 < n) :
¬ CountingResilient P f 0 f := by sorry
end PulseSyncLowerBound.Pulse.Supplement