Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 20 — 1-approximate q-counting in ⌈f/2⌉ + ⌈log₂ q⌉ − 1 rounds

Open
PulseSyncLowerBound.Pulse.Supplement.theorem_20

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributed-computingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1self-stabilisationupper-bounds

Let q≥4q\ge4q≥4 and let n∈Nn\in\mathbb Nn∈N be the number of processes. There is a deterministic finite-state protocol in the synchronous crash-fault model which, for every f∈Nf\in\mathbb Nf∈N, is an fff-resilient 111-approximate qqq-counting protocol (Definition 3) that stabilises by round

Tf=⌈f2⌉+⌈log⁡2q⌉−1.T_f=\left\lceil \frac f2\right\rceil+\lceil\log_2 q\rceil-1 .Tf​=⌈2f​⌉+⌈log2​q⌉−1.

That is, in every execution with at most fff crashes, starting from an arbitrary initial configuration, for every round t≥Tft\ge T_ft≥Tf​:

  1. (A1) the outputs of the non-faulty processes lie on a 111-path {c,c+1 mod q}\{c, c+1 \bmod q\}{c,c+1modq} of the qqq-cycle;
  2. (A2) every non-faulty process increases its output by exactly 111 modulo qqq from round ttt to round t+1t+1t+1.

No relation between nnn and fff is assumed. For q=4q=4q=4 the bound is ⌈f/2⌉+1\lceil f/2\rceil+1⌈f/2⌉+1, which matches the lower bound of Corollary 7 for every even f>0f>0f>0.

Formalization Note ⌈f/2⌉\lceil f/2\rceil⌈f/2⌉ is written (f+1)/2(f+1)/2(f+1)/2 in N\mathbb NN and ⌈log⁡2q⌉\lceil\log_2 q\rceil⌈log2​q⌉ is Nat.clog 2 q; both are the exact ceilings. The natural subtraction of 111 never truncates, since Nat.clog 2 q ≥2\ge 2≥2 for q≥4q\ge4q≥4. 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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me