Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.3 — after a lock-release phase at or after GST, correct processors lock at most one value

Proved
DLSConsensus.BasicRound.lemma_3_3

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

consensusdistributed-computingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider any run of Algorithm 1 in the basic round model whose delivery pattern is allowed for the set CCC of correct processors and the round GST\mathrm{GST}GST (every message between processors of CCC sent at a round ≥GST\ge \mathrm{GST}≥GST is delivered). Let k≥1k\ge1k≥1 with GST≤4k\mathrm{GST}\le 4kGST≤4k, so that lock-release phase kkk (round 4k4k4k) occurs at or after GST. Then, immediately after round 4k4k4k, the set

{ v∈V:some p∈C has a lock on v }\{\, v\in V : \text{some } p\in C \text{ has a lock on } v \,\}{v∈V:some p∈C has a lock on v}

contains at most one value.

This is the step of the termination proof that guarantees that, after GST, the owner of the next trying phase finds a value acceptable to all correct processors.

Formalization Note "Immediately after" is the state after the computation subround of round 4k4k4k. A processor's lock-release message to itself is subject to the same delivery rule as any other message, so it is delivered when the processor is in CCC and the round is at or after GST.

Preamble
import Mathlib
import Definitions.Def_DLSConsensus_BasicRound_Model
Formal statement
namespace DLSConsensus.BasicRound

/-- Lemma 3.3 (p. 297): immediately after any lock-release phase `k` (round `4k`) that occurs at
or after GST, the set of values locked by processors in `C` has at most one element. -/
theorem lemma_3_3 {N : ℕ} {V : Type*} (t : ℕ) (pick : ℕ → Set V → V) (init : Fin N → V)
    (C : Finset (Fin N)) (GST : ℕ) (deliv : ℕ → Fin N → Fin N → Prop)
    (hdeliv : DelivOK C GST deliv) (k : ℕ) (hk : 1 ≤ k) (hGST : GST ≤ 4 * k) :
    {v : V | ∃ p ∈ C, (exec t pick init deliv (4 * k) p).lock v ≠ none}.Subsingleton := by sorry

end DLSConsensus.BasicRound
Source
Dwork, Lynch, Stockmeyer, Consensus in the presence of partial synchrony, J. ACM 35 (1988), p. 297, Lemma 3.3
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 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