Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — linear stabilisation lower bound for pulse synchronisation

Proved
PulseSyncLowerBound.Pulse.theorem_2

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

distributed-computinglower-boundsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1self-stabilisation

Let n,f,T∈Nn,f,T\in\mathbb Nn,f,T∈N, let σ∈R\sigma\in\mathbb Rσ∈R satisfy σ≥1\sigma\ge1σ≥1, and suppose n>f+2n>f+2n>f+2. Every deterministic finite-state fff-resilient pulse synchronisation protocol of skew σ\sigmaσ that stabilises in TTT rounds must satisfy the strict bound

T+2σ>⌊f/2⌋.T+2\sigma>\lfloor f/2\rfloor.T+2σ>⌊f/2⌋.

The quantification includes all finite nonempty local state spaces, every full initial configuration, and every infinite synchronous execution with at most fff total crashes. Stabilisation means the first pulse interval starts by TTT, each non-faulty process pulses exactly once in each interval of width at most σ\sigmaσ, and consecutive intervals are separated by more than σ\sigmaσ with no intervening pulses. There is no upper frequency bound, and no assumption f>0f>0f>0.

This is an operational impossibility with the source's exact constant, including the small-fff 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
Preamble
import Definitions.Def_PulseSyncLowerBound_Pulse_Tasks
Formal statement
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
Source
Joel Rybicki, STOC 2027 submission #508 (October 2026), pinned published-basis artifact; Theorem 2; PDF p.5 / printed p.3; papers/stoc2027-508/source.pdf; SHA-256 5237f877941c17d0913977954f4f4b6ccba70f65ceae5dc47f15029dbd68765f. Repeated and proved PDF p.10 / printed p.8.
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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