OpenSearch pre-voting: pre-vote requests and responses, pre-voting rounds, the election they trigger, and the election scheduler's delays
DefinitionOpenSearchPreVoteA transcription of PreVoteCollector, the parts of Coordinator it calls, and the delay computation of ElectionSchedulerFactory, at OpenSearch revision b2a54ba5c0defba3d1d20423e911d4bf920bab19, over the per-node CoordinationState of the OpenSearchCoordination mission (whose DiscoveryNode, ClusterState, VoteCollection, ElectionStrategy, Join, CoordinationState, handleStartJoin and handleJoin are used as they are).
Messages. PreVoteRequest — the requesting node and its current term. PreVoteResponse — the responder's current term, and the term and the version (the metadata version, for a term-0 state) of its last accepted state. preVoteResponseOf cs — the response a node with coordination state cs gives: cs.currentTerm, cs.lastAcceptedTerm, cs.lastAcceptedVersionOrMetadataVersion (Coordinator.getPreVoteResponse).
Answering. CollectorState — the known leader (none when no leader is known) and the node's own response, as last set by the Coordinator (itself when it becomes leader, the leader it follows, none when it becomes a candidate). handlePreVoteRequest healthy st req — rejects if the node is not healthy; otherwise answers with st.response if the node knows no leader or knows req.sourceNode as its leader, and rejects if it knows another leader.
Rounds. PreVotingRound V — the requester's last accepted cluster state when the round started, the requester (localNode), the recorded pre-votes as a list of (sender, response) pairs, most recent first, and the flags electionStarted and isClosed. PreVotingRound.start s n — an open round over s for requester n, with no pre-votes and no election started. votes r — the vote collection built by adding the vote of each recorded sender to the empty collection (only cluster-manager-eligible senders count). isElectionQuorumFor es n t at av committed accepted votes — ElectionStrategy.isElectionQuorum with explicit arguments: votes is a quorum of committed and of accepted, and the strategy's additional constraint holds for the local node n, current term t, accepted term at and version av, the two configurations and votes.
r.handlePreVoteResponse es lr resp sender (PVC:225-279) returns the new round, whether startElection is called, and the term passed to updateMaxTermSeen (none if none is passed); lr is the requester's own current response, read when the response arrives. If the round is closed: unchanged, false, none. Otherwise, if resp is fresher than the round's accepted state s — resp.lastAcceptedTerm > s.term, or equal terms and resp.lastAcceptedVersion > s.versionOrMetadataVersion — the round is unchanged, with false and some resp.currentTerm. Otherwise the pair (sender, resp) replaces any earlier entry of sender; if the new votes are not an election quorum (isElectionQuorumFor es r.localNode lr.currentTerm lr.lastAcceptedTerm lr.lastAcceptedVersion over the last committed and last accepted configurations of s), or the round has already started an election, the result is that round with false; otherwise the round with electionStarted set, and true. In every case but the closed one, the term passed is some resp.currentTerm. close r — the round with isClosed set.
NoFresher resp s — resp.lastAcceptedTerm < s.term, or resp.lastAcceptedTerm = s.term and resp.lastAcceptedVersion ≤ s.versionOrMetadataVersion: the responses a round records. RoundReachable es Delivered — the rounds obtained from start s n (any s, n) by handling, any number of times and in any order, responses resp from senders n with Delivered n resp (each step with an arbitrary requester response lr), and by close.
The election. handleJoins es cs js — the joins of js handled in order by CoordinationState.handleJoin; a rejected join leaves the state unchanged. For joins whose term is not above the node's current term this is Coordinator.handleJoin (CO:1267-1299); a join of a higher term is rejected here (term mismatch), whereas the Coordinator first moves the node to that term (CO:1269). The joins' target is not checked (Java asserts it). startElectionTerm currentTerm maxTermSeen — max currentTerm maxTermSeen + 1, the term of the StartJoinRequest that startElection sends (CO:593). nodeMayWinElection s excluded n — n is in the last committed or the last accepted configuration of s, or is not among the excluded ids (CO:628-633); it is not used by the theorems.
The scheduler (times in milliseconds). SchedulerSettings — initialTimeout, backoffTime, maxTimeout, duration. Valid — the setting ranges (1 ≤ initialTimeout ≤ 10000, 1 ≤ backoffTime ≤ 60000, 200 ≤ maxTimeout ≤ 300000, 1 ≤ duration ≤ 300000) and the constructor's check initialTimeout ≤ maxTimeout. default — 100, 100, 10000, 500 (not used by the theorems). maxDelay s k — min(maxTimeout, initialTimeout + k · backoffTime), the bound for attempt k (counted from 0). nonNegative n — 0 for n = -2^63 (Long.MIN_VALUE), |n| otherwise. toPositiveLongAtMost r b — nonNegative r mod b + 1. attemptDelay s k r g — toPositiveLongAtMost r (maxDelay s k) + g, the delay of attempt k for the drawn random long r and the grace period g, a free parameter (Java passes 0 for the first attempt, CO:1574, and duration for the later ones, ESF:218; the field duration occurs only in Valid).
Formalization Note. The Coordinator's side effects are not modelled. The argument of updateMaxTermSeen is returned by handlePreVoteResponse, and not at all by handlePreVoteRequest (where it is always the request's term); the call's effect is outside these functions: in particular a leader whose current term is below the largest term it has seen moves to that term and starts an election, at once or, while a publication is in progress, when that publication ends (CO:560-581, CO:1784). Nodes are compared by id and role, while Java's DiscoveryNode.equals compares ephemeral ids, which change at each restart: the two can differ only between two incarnations of one node with the same role. The election strategy sees voter ids only (the per-node mission's abstraction). Health is a Boolean parameter, the network is the delivery predicate of RoundReachable, and the random long is any integer: the theorems hold for every value. Only the per-node mission's definitions are imported.
import Definitions.Def_OpenSearchCoordination
/-!
# OpenSearch cluster coordination: pre-voting and election scheduling
Before a node starts an election it runs a **pre-voting round** (`PreVoteCollector`, OpenSearch
`b2a54ba5c0defba3d1d20423e911d4bf920bab19`,
`server/src/main/java/org/opensearch/cluster/coordination/PreVoteCollector.java`, cited `PVC:<line>`): it asks the nodes
it has discovered, including itself, for a pre-vote. A node answers with its current term and the term and version of
its last accepted state, unless it is unhealthy or already follows a leader other than the requester. The round counts
the answers that are no fresher than the requester's own accepted state, and when they form an election quorum the
requester starts an election (`Coordinator.startElection`, Coordinator.java, cited `CO:<line>`): it sends a
`StartJoinRequest` in a term above every term it has seen. Pre-voting rounds are started by an **election scheduler**
(`ElectionSchedulerFactory`, cited `ESF:<line>`) at randomized, backed-off intervals.
The pre-vote messages and handlers are transcribed below as functions. Both handlers raise the Coordinator's
`maxTermSeen` (`updateMaxTermSeen`, CO:560-581): `handlePreVoteRequest` first of all, with the request's term (PVC:134);
`handlePreVoteResponse` once it has found the round open, with the response's current term, before the freshness test
(PVC:226-231). `handlePreVoteResponse` returns the term it passes (`none` when the round is closed);
`handlePreVoteRequest` returns nothing, its argument being always the request's term. When `maxTermSeen` exceeds the
current term of a leader, the leader moves to that term and starts an election itself, at once or, while a publication
is in progress, when that publication ends (CO:564-578, CO:1784); that effect is outside these functions.
Node equality: Java's `DiscoveryNode.equals` compares ephemeral ids, which change when a node restarts; here nodes are
compared by id and role. The two can differ only between two incarnations of the same node with the same role, which
Java treats as different nodes (so a follower of a node's previous incarnation with the same role refuses that node's
pre-vote request in Java, and accepts it here).
-/
namespace OpenSearchPreVote
open OpenSearchCoordination
variable {V : Type}
/-- `PreVoteRequest` (PreVoteRequest.java): the requesting node and its current term. -/
structure PreVoteRequest where
sourceNode : DiscoveryNode
currentTerm : Nat
deriving DecidableEq, Repr
/-- `PreVoteResponse` (PreVoteResponse.java): the responder's current term and the term and version (or metadata
version, for a term-0 state) of its last accepted state. -/
structure PreVoteResponse where
currentTerm : Nat
lastAcceptedTerm : Nat
lastAcceptedVersion : Int
deriving DecidableEq, Repr
/-- `Coordinator.getPreVoteResponse()` (CO:873-879): the response a node gives, computed from its coordination state. -/
def preVoteResponseOf (cs : CoordinationState V) : PreVoteResponse :=
⟨cs.currentTerm, cs.lastAcceptedTerm, cs.lastAcceptedVersionOrMetadataVersion⟩
/-- The pre-vote collector's state (PVC:79): the known leader (`none` is Java `null`, no known leader) and the node's
own response, both as last set by `update` (PVC:128-131) — `Coordinator` sets the leader to itself when it becomes
leader, to the leader it follows when it becomes a follower, and to `null` when it becomes a candidate (CO:516, 653, 777,
801, 839, 1157). Java's state is `null` before the first `update`; a node answers pre-votes only after it. -/
structure CollectorState where
leader : Option DiscoveryNode
response : PreVoteResponse
deriving DecidableEq, Repr
/-- `PreVoteCollector.handlePreVoteRequest(request)` (PVC:133-163). `healthy` is the node health status
(`nodeHealthService.getHealth()`). A node that knows a leader other than the requester refuses. (Before answering, the
handler calls `updateMaxTermSeen(request.getCurrentTerm())`, PVC:134; see the module documentation.) -/
def handlePreVoteRequest (healthy : Bool) (st : CollectorState) (req : PreVoteRequest) :
Except String PreVoteResponse :=
if !healthy then .error "rejecting on unhealthy node"
else match st.leader with
| none => .ok st.response
| some l => if l = req.sourceNode then .ok st.response else .error "rejecting as there is already a leader"
/-- A pre-voting round (`PreVoteCollector.PreVotingRound`, PVC:175-300): the last accepted cluster state of the
requester when the round started, the requester, the pre-votes received so far (Java: a map keyed by sender; here a
list, most recent first, which in every reachable round has at most one entry per sender, a sender being a node value,
id and role, as `round_entries` proves; the type itself allows repeats), whether it has started an election, and
whether it was closed.
Java takes the requester from the round's cluster state (`clusterState.nodes().getLocalNode()`, PVC:244); the request's
term (PVC:112) is not needed here. -/
structure PreVotingRound (V : Type) where
clusterState : ClusterState V
localNode : DiscoveryNode
preVotesReceived : List (DiscoveryNode × PreVoteResponse)
electionStarted : Bool
isClosed : Bool
/-- `PreVoteCollector.start` (PVC:111-115): a new, open round over the requester's last accepted state. -/
def PreVotingRound.start (s : ClusterState V) (localNode : DiscoveryNode) : PreVotingRound V :=
⟨s, localNode, [], false, false⟩
/-- The `VoteCollection` the round builds from its pre-votes (PVC:242-257): `addJoinVote` of a join from each sender,
which counts the cluster-manager-eligible senders. -/
def PreVotingRound.votes (r : PreVotingRound V) : VoteCollection :=
r.preVotesReceived.foldr (fun p v => (v.addVote p.1).1) VoteCollection.empty
/-- `ElectionStrategy.isElectionQuorum` (ElectionStrategy.java:68-88), as called with explicit arguments. -/
def isElectionQuorumFor (es : ElectionStrategy) (localNode : DiscoveryNode) (currentTerm acceptedTerm : Nat)
(acceptedVersion : Int) (committed accepted : VotingConfiguration) (votes : VoteCollection) : Bool :=
votes.isQuorum committed && votes.isQuorum accepted &&
es.satisfiesAdditionalQuorumConstraints localNode currentTerm acceptedTerm acceptedVersion committed accepted votes
/-- `PreVotingRound.handlePreVoteResponse(response, sender)` (PVC:225-279). `localResponse` is the requester's own
current response (`getPreVoteResponse()`, read when the response arrives). Returns the new round, whether
`startElection` is called, and the argument of the `updateMaxTermSeen` call (`none` when the round is closed and the
response is ignored before it). A response fresher than the round's accepted state is ignored. -/
def PreVotingRound.handlePreVoteResponse (es : ElectionStrategy) (localResponse : PreVoteResponse)
(r : PreVotingRound V) (resp : PreVoteResponse) (sender : DiscoveryNode) :
PreVotingRound V × Bool × Option Nat :=
if r.isClosed then (r, false, none)
else if resp.lastAcceptedTerm > r.clusterState.term ∨
(resp.lastAcceptedTerm = r.clusterState.term ∧
resp.lastAcceptedVersion > r.clusterState.versionOrMetadataVersion) then
(r, false, some resp.currentTerm)
else
let r₁ : PreVotingRound V :=
{ r with preVotesReceived := (sender, resp) :: r.preVotesReceived.filter (fun p => p.1 ≠ sender) }
if !isElectionQuorumFor es r.localNode localResponse.currentTerm localResponse.lastAcceptedTerm
localResponse.lastAcceptedVersion r.clusterState.lastCommittedConfiguration
r.clusterState.lastAcceptedConfiguration r₁.votes then
(r₁, false, some resp.currentTerm)
else if r₁.electionStarted then
(r₁, false, some resp.currentTerm)
else
({ r₁ with electionStarted := true }, true, some resp.currentTerm)
/-- `PreVotingRound.close()` (PVC:296-299). -/
def PreVotingRound.close (r : PreVotingRound V) : PreVotingRound V := { r with isClosed := true }
/-- A pre-vote response is no fresher than the accepted state `s`: its accepted (term, version) is lexicographically at
most `s`'s (term, version-or-metadata-version) — the responses a round counts (PVC:233-238). -/
def NoFresher (resp : PreVoteResponse) (s : ClusterState V) : Prop :=
resp.lastAcceptedTerm < s.term ∨
(resp.lastAcceptedTerm = s.term ∧ resp.lastAcceptedVersion ≤ s.versionOrMetadataVersion)
/-- The rounds a node can be in: started over any cluster state for any requester (in Java, over the requester's last
accepted state; the theorems that need this link assume it), then any sequence of responses handled — each response
from a sender and with a content allowed by `Delivered` — and possibly closed. `localResponse` (the requester's own
current response) is arbitrary at each step. -/
inductive RoundReachable (es : ElectionStrategy) (Delivered : DiscoveryNode → PreVoteResponse → Prop) :
PreVotingRound V → Prop where
| start (s : ClusterState V) (n : DiscoveryNode) : RoundReachable es Delivered (PreVotingRound.start s n)
| handle (r : PreVotingRound V) (localResponse resp : PreVoteResponse) (sender : DiscoveryNode) :
RoundReachable es Delivered r → Delivered sender resp →
RoundReachable es Delivered (r.handlePreVoteResponse es localResponse resp sender).1
| close (r : PreVotingRound V) : RoundReachable es Delivered r → RoundReachable es Delivered r.close
/-- The joins a node handles, in the order given, as `Coordinator.handleJoin` (CO:1267-1287, with
`handleJoinIgnoringExceptions`, CO:1289-1299) does for joins whose term is not above the node's current term. A join
of a higher term is rejected here (term mismatch), whereas the `Coordinator` first moves the node to that term
(CO:1269). A rejected join leaves the state unchanged: `handleJoin` throws before changing anything, and
`Coordinator.handleJoin` either propagates the exception to the joining node or ignores it. The joins' target node is
not checked (Java asserts it, CoordinationState.java:265). -/
def handleJoins (es : ElectionStrategy) (cs : CoordinationState V) (js : List Join) : CoordinationState V :=
js.foldl (fun cs j => match cs.handleJoin es j with
| .ok (cs', _) => cs'
| .error _ => cs) cs
/-- The term of the election `Coordinator.startElection` starts (CO:583-602): one above the larger of the current term
and the largest term seen. -/
def startElectionTerm (currentTerm maxTermSeen : Nat) : Nat := max currentTerm maxTermSeen + 1
/-- `Coordinator.nodeMayWinElection` (CO:628-633): the node is in the last committed or last accepted configuration,
or it is not excluded from voting. `excluded` lists the node ids of the voting-configuration exclusions. -/
def nodeMayWinElection (s : ClusterState V) (excluded : List NodeId) (n : NodeId) : Bool :=
s.lastCommittedConfiguration.nodeIds.contains n || s.lastAcceptedConfiguration.nodeIds.contains n ||
!(excluded.contains n)
/-! ## Election scheduling (`ElectionSchedulerFactory`) -/
/-- The scheduler settings, in milliseconds (ESF:85-115): `cluster.election.initial_timeout` (default 100, range
1..10000), `cluster.election.back_off_time` (default 100, range 1..60000), `cluster.election.max_timeout` (default 10000,
range 200..300000, at least the initial timeout), `cluster.election.duration` (default 500, range 1..300000). -/
structure SchedulerSettings where
initialTimeout : Nat
backoffTime : Nat
maxTimeout : Nat
duration : Nat
/-- The settings' validity (setting bounds, ESF:85-115, and the constructor check, ESF:133-143). -/
def SchedulerSettings.Valid (s : SchedulerSettings) : Prop :=
1 ≤ s.initialTimeout ∧ s.initialTimeout ≤ 10000 ∧ 1 ≤ s.backoffTime ∧ s.backoffTime ≤ 60000 ∧
200 ≤ s.maxTimeout ∧ s.maxTimeout ≤ 300000 ∧ s.initialTimeout ≤ s.maxTimeout ∧ 1 ≤ s.duration ∧ s.duration ≤ 300000
/-- The defaults. -/
def SchedulerSettings.default : SchedulerSettings := ⟨100, 100, 10000, 500⟩
/-- The bound on the delay of attempt `k` (ESF:203): `min(maxTimeout, initialTimeout + k * backoffTime)`. -/
def maxDelay (s : SchedulerSettings) (k : Nat) : Nat := min s.maxTimeout (s.initialTimeout + k * s.backoffTime)
/-- `nonNegative(n)` (ESF:159-161), defined on every integer: `-2^63` (`Long.MIN_VALUE`) maps to 0, every other `n` to
`|n|`. On a Java `long`, `n ∈ [-2^63, 2^63)`, this is Java's value. -/
def nonNegative (n : Int) : Nat := if n = -2 ^ 63 then 0 else n.natAbs
/-- `toPositiveLongAtMost(randomNumber, upperBound)` (ESF:169-172): `nonNegative(randomNumber) % upperBound + 1`, with
the natural-number remainder (for `upperBound = 0`, which Java's assertion `0 < upperBound` excludes, this is
`nonNegative(randomNumber) + 1`). -/
def toPositiveLongAtMost (randomNumber : Int) (upperBound : Nat) : Nat := nonNegative randomNumber % upperBound + 1
/-- The delay before attempt `k` fires, given the random long drawn for it and the grace period (ESF:195-204). The grace
period is a parameter: Java passes 0 for the first attempt (`Coordinator.startElectionScheduler`, CO:1574) and
`duration` for every later one (ESF:218); `SchedulerSettings.duration` is read only by `Valid`. -/
def attemptDelay (s : SchedulerSettings) (k : Nat) (randomNumber : Int) (gracePeriod : Nat) : Nat :=
toPositiveLongAtMost randomNumber (maxDelay s k) + gracePeriod
end OpenSearchPreVote
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: Def_OpenSearchPreVote.lean
This file imports Definitions.Def_OpenSearchCoordination, opens that namespace (OpenSearchCoordination), and introduces 23 declarations in the namespace OpenSearchPreVote. Throughout, is an arbitrary type (the opaque payload of a cluster state); it is implicit wherever it is not written. The imported notions these declarations use are expanded first. The declarations follow in file order.
Every declaration that cites Java was compared with the OpenSearch checkout at /home/user/opensearch-project/OpenSearch. git rev-parse HEAD there gives b2a54ba5c0defba3d1d20423e911d4bf920bab19, the revision the file cites. Each comparison is reported in a Source check line. PVC is PreVoteCollector.java, CO is Coordinator.java, ESF is ElectionSchedulerFactory.java, and all three are under server/src/main/java/org/opensearch/cluster/coordination/.
Imported notions, expanded
Node ids and discovery nodes. A node id is a natural number. A discovery node is a pair: a node id and a Boolean (isClusterManagerNode, "is cluster-manager-eligible"). Equality of discovery nodes is structural: iff and . So . Two discovery nodes with the same id but different flags are different nodes.
Voting configurations. A voting configuration is a strictly increasing list of node ids , so it has no duplicates, bundled with a proof of that fact. holds iff the list is empty. For any list of node ids,
a Boolean: strictly more than half of the configuration's ids occur in . Duplicates in and elements of outside make no difference. The empty configuration never has a quorum, because is false.
Vote collections. A vote collection is a list of node ids. is the empty list. returns a pair:
- if and ;
- otherwise.
.
Cluster states. A cluster state has these fields:
- a term ;
- a version and a metadata version ;
- a last committed configuration and a last accepted configuration ;
- an optional natural number (the cluster-manager node) and two Booleans (cluster UUID known, cluster UUID committed);
- a payload of type .
Its version-or-metadata-version is
Election strategies. An election strategy is just one arbitrary Boolean function (satisfiesAdditionalQuorumConstraints). Its arguments are a discovery node, two naturals, an integer, two voting configurations and a vote collection. The default strategy DEFAULT_INSTANCE has .
Start-join requests and joins. A start-join request is a pair (source node, term ). A join is a 5-tuple source node, target node, term , last accepted term , last accepted version .
Coordination states. A coordination state has these fields:
- a local node and a current term ;
- a last accepted state (a cluster state);
- a vote collection ;
- Booleans and ;
- an integer , a configuration and a vote collection .
The accessors used below are:
- ;
- ;
- ;
- the two configurations and .
The three coordination-state functions used here:
-
is the conjunction of:
- ;
- ;
- . The plain version is passed here, not .
Under the default strategy it is just the two quorum tests.
-
. If it returns an error. Otherwise it succeeds with a pair :
- is with: current term , last published version , last published configuration , startedJoinSinceLastReboot true, electionWon false, and both vote collections empty. The local node and the last accepted state are unchanged.
- .
-
. The guards are tested in this order, and the first that applies gives an error:
- ;
- ;
- ;
- and ;
- is empty.
If none applies, let and . Let be with joinVotes and electionWon . Let be with lastPublishedVersion set to when is true and was false, and otherwise. The result is success with .
The join's target node is never examined. Neither the current term, nor the local node, nor the last accepted state changes.
Declaration 1: PreVoteRequest
This is a structure with two fields: , a discovery node, and . Decidable equality and Repr are derived.
Source check: PreVoteRequest.java has exactly the fields DiscoveryNode sourceNode and long currentTerm (lines 50–51). The term is a natural number here instead of a Java long.
Declaration 2: PreVoteResponse
This is a structure with three fields: , and . Decidable equality and Repr are derived. Nothing relates the fields to each other; for example, is not required.
Source check: PreVoteResponse.java has the three long fields currentTerm, lastAcceptedTerm and lastAcceptedVersion (lines 48–50).
Declaration 3: preVoteResponseOf
For a coordination state :
The version component is the version-or-metadata-version. It is the metadata version when the last accepted state has term .
Source check: CO:873–879 builds new PreVoteResponse(getCurrentTerm(), getLastAcceptedTerm(), getLastAcceptedState().getVersionOrMetadataVersion()), and getCurrentTerm() (CO:882–886) reads the coordination state's current term. Matches.
Declaration 4: CollectorState
This is a structure with two fields:
- : either "none" or "some " for a discovery node ;
- : a
PreVoteResponse.
Decidable equality and Repr are derived. The type does not tie the response to any coordination state, or the leader to anything. Java's null state, before the first update, cannot be represented here: every value of this type is an initialized state.
Source check: PVC:79 declares Tuple<DiscoveryNode, PreVoteResponse> state, whose node is null when no leader is known. PVC:128–131, update, replaces both components. The docstring lists six update calls in Coordinator, and I checked each:
| Line | Leader passed to update |
|---|---|
| CO:516 | the local node (it publishes to itself) |
| CO:653 | null (joinLeaderInTerm while already a candidate) |
| CO:777 | null (becomeCandidate) |
| CO:801 | the local node (becomeLeader) |
| CO:839 | the leader node (becomeFollower) |
| CO:1157 | null (setInitialConfiguration) |
All six match the docstring.
Declaration 5: handlePreVoteRequest
It takes , a collector state and a request , and returns either an error string or a PreVoteResponse. The cases, in order:
- If : error "rejecting on unhealthy node".
- Otherwise, if : success with .
- Otherwise :
- if (same id and same flag): success with ;
- else: error "rejecting as there is already a leader".
Health is checked before the leader. On success the result is always the stored , whatever the request. is never read.
Source check: PVC:133–163 does the following in order:
- calls
updateMaxTermSeen.accept(request.getCurrentTerm()); - asserts the state is non-null;
- throws
NodeHealthCheckFailureExceptionif the status isUNHEALTHY; - returns
responseifleader == null; - returns
responseifleader.equals(request.getSourceNode()); - throws "there is already a leader" otherwise.
The order of the guards matches. Three differences:
- The
updateMaxTermSeenside effect is omitted, as the docstrings say. - Leader equality is by (id, role) instead of Java's ephemeral-id
equals, as the module docstring says. - Health is a Boolean, read as "status is not
UNHEALTHY".StatusInfo.javais not in the local checkout, so I could not confirm that the Java status has only two values.
Declaration 6: PreVotingRound V
This is a structure with five fields:
- : a cluster state;
- : a discovery node;
- : a list of pairs (sender, response);
- : a Boolean;
- : a Boolean.
No equality instance is derived. The type itself imposes nothing:
- The list may contain several entries for the same sender. The docstring's "at most one entry per sender" is not a property of the type. It is a property of the rounds the transition functions produce, and it is the second conjunct of
round_entries. - is unrelated to .
- may be true with no quorum at all.
Source check: PVC:175–300, the inner class PreVotingRound, has these fields: a concurrent map preVotesReceived keyed by DiscoveryNode, an AtomicBoolean electionStarted, a PreVoteRequest preVoteRequest, a ClusterState clusterState and an AtomicBoolean isClosed. The local node is not a field. It is read as clusterState.nodes().getLocalNode() (PVC:244 and 260). The request (with its term, PVC:112 and 184) is not represented. Java's request source is transportService.getLocalNode() (PVC:184), a different expression from the quorum's local node. This model has no request inside the round at all.
Declaration 7: PreVotingRound.start
The round has cluster state , local node , no pre-votes, no election started, and is not closed. No relation between and is required.
Source check: PreVoteCollector.start (PVC:111–115) builds a PreVotingRound(clusterState, state.v2().getCurrentTerm()) and broadcasts requests. The broadcast is not modelled. The Coordinator passes the last accepted state (CO:1608) and the discovered nodes, which include the local node (CO:1312–1317). This confirms the module docstring's "including itself".
Declaration 8: PreVotingRound.votes
The entries are processed from the end of the list (the oldest) to the front (the most recent). Each sender's id is added if the sender is cluster-manager-eligible and the id is not yet present. The result is a duplicate-free list: the ids of the eligible senders. The responses in the entries are ignored completely.
Examples:
- Entries from and give the single vote .
- An entry from alone gives no vote.
I checked both by evaluation.
Source check: PVC:242–257 builds a fresh VoteCollection and calls addJoinVote(new Join(node, localNode, …)) for every map entry. addJoinVote (CoordinationState.java:759–765) calls addVote(join.getSourceNode()). addVote (CoordinationState.java:755–757) is isClusterManagerNode() && nodes.put(id, node) == null, keyed by node id. Matches in which ids are counted. Java also records the joins, with the response's term, accepted term and version, which a plugin strategy could read. Here they are dropped.
Declaration 9: isElectionQuorumFor
For a strategy , a node , naturals and , an integer , configurations and , and a vote collection :
Source check: ElectionStrategy.java:68–88 has the final method isElectionQuorum, which is exactly joinVotes.isQuorum(lastCommitted) && joinVotes.isQuorum(lastAccepted) && satisfiesAdditionalQuorumConstraints(…all seven arguments…). Matches.
Declaration 10: PreVotingRound.handlePreVoteResponse
It takes , a "local response" , a round , a response and a sender. It returns a triple: (new round, start flag, max-term argument), where the last component is "none" or "some ". Write . The cases, in order:
- Closed. If : the result is .
- Fresher. If , or and : the result is . The response is dropped.
- Otherwise. Let be with
Any earlier entry from a sender equal to this one (same id and same flag) is removed, and the new entry is put in front. Let
- (a) If is false: .
- (b) Else if (which equals ): .
- (c) Else: .
Consequences that can be read off:
- The start flag is true only in case 3(c).
- The third component is "none" exactly in the closed case.
- The round's cluster state, local node and closed flag never change.
- The entry is stored even when the sender is not cluster-manager-eligible. Such a sender then contributes no vote.
- enters only as the strategy's term and version arguments, so under the default strategy it is irrelevant.
I checked by evaluation that a fresher response leaves the list unchanged and still reports its current term, and that a closed round reports "none".
Source check: PVC:225–279 does the following in order:
- returns if closed (PVC:226–229);
- calls
updateMaxTermSeen.accept(response.getCurrentTerm())(PVC:231); - returns on the fresher test (PVC:233–238);
- calls
preVotesReceived.put(sender, response)(PVC:240); - rebuilds the votes;
- tests
electionStrategy.isElectionQuorum(localNode, localPreVoteResponse.getCurrentTerm(), …getLastAcceptedTerm(), …getLastAcceptedVersion(), lastCommitted, lastAccepted, voteCollection), wherelocalPreVoteResponse = getPreVoteResponse()is the collector's current state (PVC:245); - does
electionStarted.compareAndSet(false, true)and callsstartElection.run().
Matches, including that the max-term argument is reported in the fresher case. Java's map put replaces by ephemeral-id equality. The filter here removes by (id, role) equality, as the module docstring says.
Declaration 11: PreVotingRound.close
is with . It is idempotent here.
Source check: PVC:296–299 does isClosed.compareAndSet(false, true) and asserts that it was not already closed. The assertion is not modelled.
Declaration 12: NoFresher
For a response and a cluster state , is the proposition
This is lexicographic of against . It is exactly the negation of the "fresher" guard of Declaration 10, case 2.
Source check: the docstring cites PVC:232–238. The test is at PVC:233–238 (232 is blank). Matches.
Declaration 13: RoundReachable
Fix a strategy and an arbitrary predicate on (discovery node, response) pairs. is the least predicate on rounds that is closed under three rules:
- start: for every cluster state and node , is reachable;
- handle: if is reachable and holds, then for every , the first component of is reachable;
- close: if is reachable, so is .
Consequences of this definition:
- is one fixed predicate for the whole run. It does not depend on time or on the round.
- The local response is chosen freely at each step.
- A sender can deliver any number of times, with different responses each time. Senders need not be among any requested nodes.
- Handle and close steps interleave freely. A handle step after close is a no-op, and close can be repeated.
- The start state and the local node are arbitrary and unrelated to each other.
- Along any derivation the round's cluster state and local node stay those given at start.
The docstring says "started over its accepted state". Nothing in the term makes anyone's accepted state.
Declaration 14: handleJoins
The joins are applied from left to right, each to the state the previous one produced. A rejected join leaves the state unchanged, and the "added" Boolean is discarded. A join whose term is above the current term is simply rejected by guard 1 of handleJoin. Nothing moves the state to that term. Nothing checks the joins' target node.
Source check: Coordinator.handleJoin (CO:1267–1287) first calls ensureTermAtLeast(…, join.getTerm()), which only matters for a higher term (CO:1269). It then calls CoordinationState.handleJoin either through handleJoinIgnoringExceptions (CO:1292–1299) when the election is already won, or directly. In CoordinationState.handleJoin (CoordinationState.java:264–339) every rejection throws before the first mutation (the throws are at lines 269–317; the vote is added at line 320). So "a rejected join leaves the state unchanged" is correct. Java asserts join.targetMatches(localNode) (line 265); that assertion is not modelled. The docstring restricts the claim to joins whose term is not above the current term. The definition itself imposes no such restriction.
Declaration 15: startElectionTerm
Source check: CO:593 builds new StartJoinRequest(getLocalNode(), Math.max(getCurrentTerm(), maxTermSeen) + 1). Matches. Java's guards (mode == CANDIDATE and localNodeMayWinElection, CO:587–591) and the sending to discovered non-Zen1 nodes (CO:595–599) are not part of this definition.
Declaration 16: nodeMayWinElection
For a cluster state , a list of node ids and a node id :
The exclusions are a separate argument, unrelated to . No theorem of this mission uses this definition.
Source check: CO:628–633 matches, with getVotingConfigExclusions().stream().noneMatch(…) as .
Declaration 17: SchedulerSettings
This is a structure with four natural-number fields: , , and . The docstring says they are milliseconds. The type carries no unit and no bounds.
Source check: the setting keys (ESF:66–69) are cluster.election.initial_timeout, back_off_time, max_timeout and duration. Their defaults and bounds (ESF:85–115) are:
| Setting | Default | Range |
|---|---|---|
| initial_timeout | 100 ms | 1 ms – 10 s |
| back_off_time | 100 ms | 1 ms – 60 s |
| max_timeout | 10 s | 200 ms – 300 s |
| duration | 500 ms | 1 ms – 300 s |
These match the docstring. Java reads them as TimeValue.millis().
Declaration 18: SchedulerSettings.Valid
is the conjunction:
- ;
- ;
- ;
- ;
- .
Source check: these are the setting bounds above, plus the constructor check at ESF:133–143 (it throws if maxTimeout.millis() < initialTimeout.millis()). Matches. Setting.java is not in the local checkout, so I could not see how the bounds are checked for sub-millisecond TimeValues.
Declaration 19: SchedulerSettings.default
, that is: initialTimeout , backoffTime , maxTimeout , duration . These match the Java defaults, and the value satisfies . No theorem of this mission uses it.
Declaration 20: maxDelay
in unbounded natural-number arithmetic, so there is no overflow. With the defaults it is up to , where it first reaches ; I checked this by evaluation. Without it can be , for example with initialTimeout and backoffTime .
Source check: ESF:203 is Math.min(maxTimeout.millis(), initialTimeout.millis() + thisAttempt * backoffTime.millis()), where thisAttempt counts from (ESF:201). Matches. The Java comment there notes that overflow would take "over a million years".
Declaration 21: nonNegative
For any integer :
-2 ^ 63 parses as , which is Long.MIN_VALUE. I confirmed the parse with pp.parens; since is odd, would give the same value anyway.
The domain is all of , not only Java's long range. Outside the function returns , for example . No Java long gives such a value. The docstring states the long range, but the definition does not restrict to it.
Source check: ESF:159–161 is n == Long.MIN_VALUE ? 0 : Math.abs(n). Matches on longs.
Declaration 22: toPositiveLongAtMost
For an integer and :
with natural-number .
- For the result is in .
- For , Lean's returns the dividend, so the result is . Java asserts
0 < upperBound, and Java's%by zero would throw. The definition leaves this case defined but meaningless.
Source check: ESF:169–172. Matches for .
Declaration 23: attemptDelay
For settings , an attempt index , an integer (the random long) and a grace period :
The docstring says is for the first attempt and for later ones. The definition takes as a free argument, and nothing ties it to or to . In fact is read by no definition of the file except .
Source check: ESF:195–204 computes delayMillis = toPositiveLongAtMost(random.nextLong(), maxDelayMillis) + gracePeriod.millis(). Later attempts are rescheduled with scheduleNextElection(duration, …) (ESF:218). The first grace period is TimeValue.ZERO (CO:1574). Matches.
Remarks on the docstrings
- Module docstring, "Both handlers first raise the Coordinator's
maxTermSeen."handlePreVoteResponsetests the closed flag first and raises the term only if the round is open. Its own docstring and code say so correctly; the module sentence is loose. - Module docstring, "the leader moves to that term and starts an election itself (CO:565-577)." In Java this happens only when no publication is in progress; otherwise the term bump is deferred (CO:567–568). If the bump fails, the node becomes a candidate (CO:574–576). The docstring places this effect outside the functions, and no definition models it.
- Module docstring on node equality. It says the Lean and Java comparisons "agree except between two incarnations of the same node". Two incarnations with different roles are distinct under both comparisons. The real disagreement is between two incarnations with the same id and role.
PreVotingRound, "at most one entry per sender." This is not a type invariant (see Declaration 6). "Sender" here means a discovery-node value, that is, an (id, role) pair, so two entries may share an id. I checked by evaluation: senders and both stay in the list.RoundReachable, "started over its accepted state." The start rule accepts any cluster state.nonNegative, "on a Javalong." The definition is total on .attemptDelay, the grace-period description. This describes how Java calls the function. The grace period is a free parameter here.- Unused declarations. No theorem of this mission uses
nodeMayWinElectionorSchedulerSettings.default.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.