Theorem 20 — 1-approximate q-counting in ⌈f/2⌉ + ⌈log₂ q⌉ − 1 rounds
OpenPulseSyncLowerBound.Pulse.Supplement.theorem_20distributed-computingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1self-stabilisationupper-bounds
Let and let be the number of processes. There is a deterministic finite-state protocol in the synchronous crash-fault model which, for every , is an -resilient -approximate -counting protocol (Definition 3) that stabilises by round
That is, in every execution with at most crashes, starting from an arbitrary initial configuration, for every round :
- (A1) the outputs of the non-faulty processes lie on a -path of the -cycle;
- (A2) every non-faulty process increases its output by exactly modulo from round to round .
No relation between and is assumed. For the bound is , which matches the lower bound of Corollary 7 for every even .
Formalization Note is written in and is Nat.clog 2 q; both are the exact ceilings. The natural subtraction of never truncates, since Nat.clog 2 q for . The protocol may use any finite nonempty local state sets of the base model.
Differences from the source:
- generalization: for each f there is an f-resilient protocol stabilising by round ⌈f/2⌉+⌈log₂ q⌉−1 → one protocol (for given n, q) that is f-resilient with that bound simultaneously for every f; reason: the §7.1 protocol does not depend on f, and instantiating the universal f gives the source's statement for each f
- 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; the source's protocol has state set Z_q, which is finite and nonempty for q ≥ 4
- encoding: ⌈f/2⌉ and ⌈log₂ q⌉ → (f + 1) / 2 and Nat.clog 2 q in ℕ; reason: exact ceilings for all f and all q ≥ 1; the subtraction of 1 is not truncated because Nat.clog 2 q ≥ 2 for q ≥ 4
Preamble
import Definitions.Def_PulseSyncLowerBound_Pulse_Supplement_ApproxCounting
Formal statement
namespace PulseSyncLowerBound.Pulse.Supplement
open PulseSyncLowerBound.Pulse
attribute [local instance] Classical.propDecidable Classical.decEq
theorem theorem_20 (n q : ℕ) (hq : 4 ≤ q) :
∃ P : Protocol n (Fin q), ∀ f : ℕ,
ApproxCountingResilient P f 1 ((f + 1) / 2 + Nat.clog 2 q - 1) := by sorry
end PulseSyncLowerBound.Pulse.Supplement
Source
Joel Rybicki, STOC 2027 submission #508 (October 2026), pinned published-basis artifact; Theorem 20; PDF p.27 / printed p.25 (protocol and Lemmas 18–19: PDF pp.26–27 / printed pp.24–25); papers/stoc2027-508/source.pdf; SHA-256 5237f877941c17d0913977954f4f4b6ccba70f65ceae5dc47f15029dbd68765f. Definition 3: PDF p.6 / printed p.4.