Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A round counts exactly its cluster-manager-eligible senders

Proved
OpenSearchPreVote.votes_mem

by pitimespi · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

cluster-coordinationconsensuselasticsearchelection-schedulerformal-verificationleader-electionopensearchpaxospre-voteraftzen2

For every pre-voting round r and node id x: x is among the ids of r.votes iff some recorded entry p ∈ r.preVotesReceived has p.1.id = x and p.1.isClusterManagerNode = true. The votes of a round are the ids of its recorded senders that have the cluster-manager role.

Preamble
import Definitions.Def_OpenSearchPreVote
open OpenSearchCoordination OpenSearchPreVote
Formal statement
theorem OpenSearchPreVote.votes_mem {V : Type} (r : PreVotingRound V) (x : NodeId) :
    x ∈ r.votes.nodes ↔ ∃ p ∈ r.preVotesReceived, p.1.id = x ∧ p.1.isClusterManagerNode = true := by sorry
Source
OpenSearch b2a54ba5c0defba3d1d20423e911d4bf920bab19: PreVoteCollector (state line 79, start 111-115, update 128-131, handlePreVoteRequest 133-163, PreVotingRound 175-300, handlePreVoteResponse 225-279, close 296-299): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/PreVoteCollector.java#L66-L301; Coordinator (updateMaxTermSeen lines 560-581, startElection 583-602, nodeMayWinElection 628-633, getPreVoteResponse 873-879, handleJoin 1267-1299, startElectionScheduler 1567-1618, the preVoteCollector.update calls 516, 653, 777, 801, 839, 1157): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/Coordinator.java#L560-L633; ElectionSchedulerFactory (settings lines 85-115, constructor check 133-143, nonNegative 159-161, toPositiveLongAtMost 169-172, scheduleNextElection 195-241): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionSchedulerFactory.java#L62-L254; ElectionStrategy.isElectionQuorum (lines 68-88): https://github.com/opensearch-project/OpenSearch/blob/b2a54ba5c0defba3d1d20423e911d4bf920bab19/server/src/main/java/org/opensearch/cluster/coordination/ElectionStrategy.java#L68-L88; the messages PreVoteRequest.java and PreVoteResponse.java in the same directory; CoordinationState (handleStartJoin, handleJoin) as transcribed by the OpenSearchCoordination mission
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: OpenSearchPreVote.votes_mem

Notions used

Discovery nodes. A discovery node nnn is a pair: a node id n.id∈Nn.\mathrm{id} \in \mathbb{N}n.id∈N and a Boolean n.cmn.\mathrm{cm}n.cm ("cluster-manager-eligible").

Pre-voting rounds. A round rrr has five fields:

  • a cluster state;
  • a local node;
  • a list r.preVotesReceivedr.\mathrm{preVotesReceived}r.preVotesReceived of pairs (sender,response)(\mathit{sender}, \mathit{response})(sender,response);
  • two Booleans, electionStarted\mathrm{electionStarted}electionStarted and isClosed\mathrm{isClosed}isClosed.

Vote collections and votes(r)\mathrm{votes}(r)votes(r). A vote collection is a list of node ids. addVote(v,n)\mathrm{addVote}(v, n)addVote(v,n) prepends n.idn.\mathrm{id}n.id to vvv when n.cmn.\mathrm{cm}n.cm is true and n.idn.\mathrm{id}n.id is not already in vvv; otherwise it leaves vvv unchanged. votes(r)\mathrm{votes}(r)votes(r) is computed as follows:

  • start from the empty collection;
  • fold addVote\mathrm{addVote}addVote over the senders of r.preVotesReceivedr.\mathrm{preVotesReceived}r.preVotesReceived, from the last entry to the first (foldr);
  • the responses play no part.

1. Declaration

Binders. There are no hypotheses.

  • VVV: an implicit type;
  • rrr: a pre-voting round over VVV, completely arbitrary (not assumed reachable);
  • xxx: a node id.

Conclusion.

x∈votes(r).nodes  ⟺  ∃ p∈r.preVotesReceived, p.1.id=x∧p.1.cm=true.x \in \mathrm{votes}(r).\mathrm{nodes} \iff \exists\, p \in r.\mathrm{preVotesReceived},\ p.1.\mathrm{id} = x \wedge p.1.\mathrm{cm} = \mathrm{true}.x∈votes(r).nodes⟺∃p∈r.preVotesReceived, p.1.id=x∧p.1.cm=true.

The vote collection of the round contains the id xxx exactly when some received entry has a sender with id xxx that is cluster-manager-eligible.

2. What is not constrained

  • The round. rrr is arbitrary. The list may contain repeated senders, or two senders with the same id and different flags (for example ⟨5,false⟩\langle 5,\mathrm{false}\rangle⟨5,false⟩ and ⟨5,true⟩\langle 5,\mathrm{true}\rangle⟨5,true⟩, which give the vote 555 through the second). The round may be closed or started.
  • Order and multiplicity. The statement is about membership only. It says nothing about the order or multiplicity of votes(r).nodes\mathrm{votes}(r).\mathrm{nodes}votes(r).nodes. By construction the list has no duplicates, but the theorem does not state it.
  • The responses. The responses p.2p.2p.2 do not occur. Their terms and versions do not affect which ids count.
  • Vacuity. There are no hypotheses, so nothing can be vacuous.

3. Plain-language summary

The ids counted as votes by a pre-voting round are exactly the ids of the cluster-manager-eligible senders that appear in its list of received pre-votes. Ineligible senders and the contents of the responses contribute nothing.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 1, 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