OpenSearch coordination as a message-passing system: every node runs CoordinationState, messages may be lost, duplicated or reordered, nodes restart; the safety vocabulary and the inductive invariant
DefinitionOpenSearchSafetyA model of an OpenSearch cluster at revision b2a54ba5c0defba3d1d20423e911d4bf920bab19 in which every node runs the CoordinationState of the OpenSearchCoordination mission (its NodeId, DiscoveryNode, VotingConfiguration, ClusterState, message types, ElectionStrategy, CoordinationState, handlers and contracts are used as they are), the notions in which the safety theorems are stated, and the inductive invariant Inv from which they are proved. CO is Coordinator.java, CBS is ClusterBootstrapService.java.
Messages. Message V — join j, a Join; publishRequest source state parentTerm parentVersion, a PublishRequest of state from source, together with ghost data that the real message does not carry: the term and version of the state the publisher had accepted when it published, the publication's parent; publishResponse source dest resp, a PublishResponse from source to dest; applyCommit c, an ApplyCommitRequest.
Parameters. Params — eligible n, whether node n has the cluster-manager role (DiscoveryNode.isClusterManagerNode(), fixed); initConfs, the configurations a node may bootstrap with (a predicate on configurations); strategy, the election strategy of every node. P.dn n — the DiscoveryNode ⟨n, P.eligible n⟩. P.InitCompatible — for all configurations X, Y with P.initConfs X and P.initConfs Y and all lists q₁, q₂ of eligible node ids with X.hasQuorum q₁ and Y.hasQuorum q₂, some node id is in both lists. BootstrapConfig k resolve placeholder matched X — X has the form of a configuration that ClusterBootstrapService bootstraps with (CBS:176-215, 259-273, 306-335): the k bootstrap requirements (cluster.initial_cluster_manager_nodes) are numbered 0 … k-1; the members of X are exactly, for i < k, resolve i if matched i (the node has discovered the node requirement i names) and the placeholder id placeholder i otherwise ("{bootstrap-placeholder}-" + requirement); and more than half of the k requirements are matched. The predicate does not require resolve or placeholder to be injective or their values to be distinct (bootstrap_compatible assumes this; in Java the requirements have no duplicates and checkRequirements matches each requirement and each discovered node at most once, CBS:150-155, 306-335), nor the bootstrapping node to be eligible and matched (Java requires both, CBS:179, 202-209); no other definition refers to it (the bootstrap step uses P.initConfs).
Clusters. Cluster V — node : NodeId → CoordinationState V, the state of every node, and sent : Message V → Prop, the messages sent so far. W.set n cs replaces node n's state by cs; W.send m adds m to the sent messages. Initial P W — every node n is CoordinationState.init (P.dn n) 0 s for some cluster state s of term 0 whose last committed and last accepted configurations are empty (its other fields, version and metadata version included, are arbitrary), and no message has been sent. RestartState s s' — the accepted state s' a restarting cluster-manager-eligible node comes back with, given the accepted state s it had: s' has the term, the version, the two configurations and the two cluster-UUID flags of s (its metadata version, cluster-manager node and payload may differ: Java rebuilds the cluster-manager node and the parts of the state outside the persisted metadata, and leaving the persisted metadata, metadata version included, free only adds behaviours); or s has term 0, empty configurations and an unknown cluster UUID, and s' has term 0 and empty configurations (a node that never joined a cluster, restoring a state from the remote store).
Steps. Step P W W' — one successful handler call at a node n, its output, if any, being added to the sent messages:
bootstrap:(W.node n).setInitialState s = .ok cs'for a stateswhose two configurations are someXwithP.initConfs X, withinitialStateContract(the method's asserted preconditions);W' = W.set n cs';startJoin:handleStartJoin ⟨P.dn src, t⟩ = .ok (cs', j)for any eligiblesrcand any termt;W' = (W.set n cs').send (.join j);join:handleJoin P.strategy j = .ok (cs', b)for a sent joinjwithj.targetNode.id = n;W' = W.set n cs';clientValue:handleClientValue s = .ok (cs', p)withclientValueContract(the asserted precondition:scarriesn's last committed configuration); sendspublishRequest n p.acceptedState lt lv, where(lt, lv)aren's last accepted term and version before the call;publish:handlePublishRequest ⟨s⟩ = .ok (cs', r)for a sentpublishRequest src s pt pv; sendspublishResponse n src r;respond:handlePublishResponse (P.dn src) r = .ok (cs', o)for a sentpublishResponse src n r; sendsapplyCommit cifo = some c;commit:handleCommit c = .ok cs'for a sentapplyCommit c;restart: for an eligiblen, the state becomesCoordinationState.init (W.node n).localNode (W.node n).currentTerm s'for a states'withRestartState (W.node n).lastAcceptedState s';restartAny: for a nodenthat is not eligible, the state becomesCoordinationState.init (W.node n).localNode t s'for any termtand any states'.
Reachable P W — W is initial, or is reached from a reachable cluster by a step.
Safety vocabulary. A publication is named by its key, its (term, version). Committed W t v — some applyCommit ⟨src, t, v⟩ has been sent. Parent W t v t' v' — some publishRequest src s t v with s.term = t' and s.version = v' has been sent. Descends W t v t' v' — the reflexive-transitive closure of Parent: (t', v') descends from (t, v).
Proof-side notions (used by Inv, the lemmas and their proofs only; Published appears only in the proofs). KeyLE t v t' v' — t < t' ∨ (t = t' ∧ v ≤ v'). Below lt lv bt bv — lt < bt ∨ (lt = bt ∧ (bt = 0 ∨ lv ≤ bv)): handleJoin's freshness comparison, ignoring the version at term 0, where joins carry metadata versions. Published W t v — some publication of term t and version v has been sent. Realizes P W t v x y — the pair (last committed, last accepted) (x, y) realizes the key (t, v): t = 0, x = y and P.initConfs x (a bootstrap state); or some sent publication of term t and version v has last accepted configuration y, and last committed configuration x, or last accepted configuration x with (t, v) committed. JoinVoters P W L t J — every member of J is eligible and sent node L a join of term t. BaseVoters P W L t bt bv J — every member of J is eligible and sent L a join of term t whose last accepted term and version are Below bt bv. RespVoters P W t v A — every member of A is eligible and sent a PublishResponse for (t, v) to some node. ElectionRecord P W L t bt bv x y J — bt < t, Realizes P W bt bv x y, BaseVoters P W L t bt bv J, x.hasQuorum J and y.hasQuorum J: an election of L in term t over the base (bt, bv). Won P W b t — b is eligible, and either (W.node b).electionWon = true with current term t, or b has sent a publication of term t.
Inv P W — the inductive invariant, 30 facts (field names in parentheses).
- Every node
n: its local node isP.dn n(localNode_eq); if it has not won, its last published version is 0 and its publish votes are empty (idle_of_not_won); if it has won, and if it holds join votes, it has handled a start-join since its last restart (won_started,votes_started); if it has handled one, its current term is at least 1 (started_term_pos); its join votes are a quorum of both its last committed and its last accepted configuration if it has won (won_quorum) and not if it has not (not_won_no_quorum); every join vote it holds is of an eligible node that sent it a join for its current term with a last accepted term and versionBelowits own (joinVotes_sent); every publish vote it holds is of an eligible node that sent it aPublishResponsefor its current term and last published version (publishVotes_sent). - Every eligible node: its last accepted term is at most its current term (
term_le); its accepted state has term 0 and empty configurations, or its two configurations realize its last accepted term and version (accepted_realizes). - Joins and responses: every join is from the
DiscoveryNodeof its source and addressed to an eligible node (join_wf); the joins of an eligible node have terms at most its current term (join_term_le), at most one per term (join_unique), and a join of an eligible node for a term later than one of its publish responses carries a last accepted (term, version) at least the response's (join_after_response); the publish responses of an eligible node have terms at most its current term and keys at most its last accepted key (response_le); every publish response answers a publication of its key sent by the node it is addressed to (response_published). - Publications: every publication is sent by an eligible node, has term ≥ 1, a parent of term at most its term and of smaller version, and, if the parent has term 0, a bootstrap configuration as last committed configuration (
pub_wf); a parent of term ≥ 1 is the key of a sent publication, the last committed configuration is that publication's last committed one, or its last accepted one if the parent is committed, and the last accepted configuration differs from that publication's only if the last committed configuration is that publication's last accepted one (pub_parent); two publications with the same key are the same message (pub_unique); every publication descends from a key of term 0 (pub_rooted); two publications of the same term are related by descent (pub_same_term); the eligible nodes that sent the publisher a join for the publication's term include a quorum of both its configurations (pub_voters); a publication whose parent is of an older term carries an election record of its publisher for its term, over the parent, with its last committed configuration asx(pub_election). - Commits: every commit is of a sent publication whose publish responses from eligible nodes include a quorum
Aof its last accepted configuration such thatAis also a quorum of its last committed configuration, or the publication's parent is committed and is a sent publication with the same last accepted configuration (commit_quorum). - Leaders: for each term
t, at most one nodebhasWon P W b t(won_unique); a node that published in a term is past that term, or still in it and either elected or without a start-join handled since its last restart (pub_source_term); every publication of an elected node's current term has a version at most the node's last published version, descends to (current term, last published version), and has both configurations with a quorum in the node's join votes (leader_pubs); an elected node whose last published version differs from its last accepted version sent a publication of key (current term, last published version) with its accepted key as parent, its last published configuration is that publication's last accepted configuration, and its last committed configuration is that publication's last committed one, or that publication's last accepted one with its accepted key committed and its last accepted configuration equal to that publication's (leader_inflight); an elected node whose last published version equals its last accepted version has its last accepted term equal to its current term and its last published configuration equal to its last accepted one, or an older last accepted term while no publication of its current term has been sent (leader_settled).
Formalization Note. Messages are never removed: a step may handle any sent message any number of times, in any order, or never, which models loss, duplication, delay and reordering. A join is handled only by its target and a publish response only by its addressee; publish requests and commits may be handled by any node. Start-join requests are not messages: any node may handle a request from any eligible node for any term at any time, which covers the Coordinator's elections, abdication and ensureTermAtLeast (CO:583-657) and over-approximates them; the Coordinator's other guards only reject more calls. The asserted preconditions of setInitialState and handleClientValue are imposed at the bootstrap and clientValue steps. The ghost parent of a publication is not read by any handler. A cluster-manager-eligible node persists its current term and accepted state synchronously; a restart keeps its current term and either keeps its accepted state except for the metadata version, the cluster-manager node and the payload, which it leaves free, or, if the node never joined a cluster (term 0, empty configurations, unknown cluster UUID), replaces it by a term-0 state with empty configurations, as restored from the remote store (RestartState); a node that is not cluster-manager-eligible may come back with any term and state. Outside the model (assumptions): a node's cluster-manager role never changes; persisted state is never rolled back; the offline opensearch-node tools are not used; bootstrap requirements name the same node at every node; every node uses the same election strategy; a publication delivered through the remote cluster-state store reconstructs exactly the published state. The per-node abstractions of OpenSearchCoordination apply (terms are naturals, versions integers without overflow, the remote persisted state omitted). The safety theorems assume P.InitCompatible and P.strategy = ElectionStrategy.DEFAULT_INSTANCE. The file imports only the OpenSearchCoordination definitions (Lean core).
import Definitions.Def_OpenSearchCoordination
/-!
# OpenSearch cluster coordination: the cluster
Every node runs the `CoordinationState` of `Def_OpenSearchCoordination` (OpenSearch
`b2a54ba5c0defba3d1d20423e911d4bf920bab19`). Nodes exchange messages through a network that may lose, duplicate, delay
and reorder them: a message, once sent, stays available forever and may be handled any number of times, by any node it
is addressed to, or never. Nodes may crash and restart at any time.
Each step is a successful call of one `CoordinationState` method, its output, if any, being sent. The steps cover every
call the `Coordinator` makes (`Coordinator.java`, cited `CO:<line>`; the `Coordinator`'s own guards only reject more):
* `bootstrap`: `setInitialState` with a bootstrap configuration (`ClusterBootstrapService`, CO:1101-1161), under the
method's asserted preconditions; nodes may bootstrap with different configurations (`BootstrapConfig` describes
`ClusterBootstrapService`'s configurations; the model does not refer to it);
* `startJoin`: `handleStartJoin` for a request from any cluster-manager-eligible node in any term (elections, abdication,
and `ensureTermAtLeast` on receiving a message of a higher term, which joins that message's sender); the `Join` is
sent to the requester;
* `join`: `handleJoin` of a sent `Join` addressed to the node;
* `clientValue`: `handleClientValue` of any cluster state satisfying the asserted precondition; the `PublishRequest` is
sent to every node;
* `publish`: `handlePublishRequest` of a sent `PublishRequest`; the `PublishResponse` goes back to the publisher;
* `respond`: `handlePublishResponse` of a sent `PublishResponse` addressed to the node; a resulting `ApplyCommitRequest`
is sent to every node;
* `commit`: `handleCommit` of a sent `ApplyCommitRequest`;
* `restart`: a new `CoordinationState` over the persisted state. A cluster-manager-eligible node persists its current
term and accepted state synchronously (`GatewayMetaState.LucenePersistedState`) and rebuilds on startup the parts of
the accepted state that are not persisted (the node list, routing table, transient settings;
GatewayMetaState.java:164-197); the model leaves the metadata version, the cluster-manager node and the payload free,
which only adds behaviours. A node that never joined a cluster (term 0, empty configurations, unknown cluster UUID)
may instead come back with a term-0 state with empty configurations, as restored from the remote store
(GatewayMetaState.java:169-188). A node that is not cluster-manager-eligible persists asynchronously or not at all,
and may come back with any persisted state.
A `PublishRequest` records, as ghost data that the real message does not carry, the term and version of the state its
publisher had accepted when it published (its parent); this defines descent between published states.
OpenSearch's randomized safety test `CoordinationStateTestCluster` (`test/framework/.../coordination/`) runs random
executions of a similar model (messages are never removed, start-join requests carry arbitrary terms, any elected node
publishes arbitrary values and configurations, and nodes reboot) and checks the assertions of `invariant()` at every
node and, at the end, one cluster-manager per term and one cluster state per (term, version).
Assumptions (outside the model): the cluster-manager role of a node never changes (changing it and back can reset the
persisted term, GatewayMetaState.java:232-255); no disk rollback; no offline tools (`opensearch-node` unsafe-bootstrap,
detach-cluster, remove-settings, remove-customs); bootstrap requirements name the same node at every node; one election
strategy for all nodes; a publication delivered through the remote store reconstructs exactly the published state.
-/
namespace OpenSearchSafety
open OpenSearchCoordination
/-- Messages. -/
inductive Message (V : Type) where
| join (j : Join)
/-- A `PublishRequest` from `source`, with the ghost parent (term, version). -/
| publishRequest (source : NodeId) (state : ClusterState V) (parentTerm : Nat) (parentVersion : Int)
/-- A `PublishResponse` from `source` to `dest`. -/
| publishResponse (source dest : NodeId) (resp : PublishResponse)
| applyCommit (c : ApplyCommitRequest)
/-- The fixed parameters of a cluster. -/
structure Params where
/-- `DiscoveryNode.isClusterManagerNode()` of each node. -/
eligible : NodeId → Bool
/-- The configurations a node may bootstrap with. -/
initConfs : VotingConfiguration → Prop
/-- The election strategy of every node. -/
strategy : ElectionStrategy
/-- The `DiscoveryNode` of node `n`. -/
def Params.dn (P : Params) (n : NodeId) : DiscoveryNode := ⟨n, P.eligible n⟩
/-- The bootstrap configurations are compatible: votes of cluster-manager-eligible nodes that form a quorum of one
bootstrap configuration share a voter with votes that form a quorum of another. -/
def Params.InitCompatible (P : Params) : Prop :=
∀ X Y, P.initConfs X → P.initConfs Y → ∀ q₁ q₂ : List NodeId,
(∀ x ∈ q₁, P.eligible x = true) → (∀ x ∈ q₂, P.eligible x = true) →
X.hasQuorum q₁ = true → Y.hasQuorum q₂ = true → ∃ x, x ∈ q₁ ∧ x ∈ q₂
/-- The form of the configurations `ClusterBootstrapService` bootstraps with (CBS:176-215, CBS:259-273, CBS:306-335):
the bootstrap requirements (`cluster.initial_cluster_manager_nodes`, without duplicates) are numbered `0 … k-1`;
requirement `i`, when the node has discovered the node it names, contributes that node's id `resolve i`, and otherwise a
placeholder id `placeholder i` (`"{bootstrap-placeholder}-" + requirement`); more than half of the requirements must be
matched. The predicate does not require `resolve` or `placeholder` to be injective or their values to be distinct
(`bootstrap_compatible` assumes this), nor the bootstrapping node to be eligible and matched (Java requires both,
CBS:179, 202-209). No other definition refers to it: the `bootstrap` step uses `P.initConfs`. -/
def BootstrapConfig (k : Nat) (resolve placeholder : Nat → NodeId) (matched : Nat → Bool)
(X : VotingConfiguration) : Prop :=
(∀ x, x ∈ X.nodeIds ↔ ∃ i, i < k ∧ x = if matched i then resolve i else placeholder i) ∧
((List.range k).filter matched).length * 2 > k
/-- A cluster: the coordination state of every node and the set of messages sent so far. -/
structure Cluster (V : Type) where
node : NodeId → CoordinationState V
sent : Message V → Prop
namespace Cluster
variable {V : Type}
/-- Replace node `n`'s state. -/
def set (W : Cluster V) (n : NodeId) (cs : CoordinationState V) : Cluster V :=
{ W with node := fun m => if m = n then cs else W.node m }
/-- Send a message. -/
def send (W : Cluster V) (m : Message V) : Cluster V := { W with sent := fun x => W.sent x ∨ x = m }
end Cluster
variable {V : Type}
/-- A fresh cluster: every node is in term 0 with an accepted term-0 state with empty configurations (its version,
metadata version, cluster-manager node, cluster-UUID flags and payload are arbitrary and may differ between nodes — a
fresh node has version 0, a node restored from the remote store or upgraded from an older version may have others),
and no message has been sent. -/
def Initial (P : Params) (W : Cluster V) : Prop :=
(∀ n, ∃ s : ClusterState V, s.term = 0 ∧ s.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
s.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
W.node n = CoordinationState.init (P.dn n) 0 s) ∧
(∀ m, ¬ W.sent m)
/-- The accepted state a restarting cluster-manager-eligible node comes back with, given the one it had: the persisted
term, version, configurations and cluster-UUID flags, with the rest (metadata version, cluster-manager node, payload)
left free — Java rebuilds the cluster-manager node and the parts of the state outside the persisted metadata, and
leaving the persisted metadata free only adds behaviours; or, if it never joined a cluster (term 0, empty
configurations, unknown cluster UUID), a term-0 state with empty configurations, as restored from the remote store. -/
def RestartState (s s' : ClusterState V) : Prop :=
(s'.term = s.term ∧ s'.version = s.version ∧
s'.lastCommittedConfiguration = s.lastCommittedConfiguration ∧
s'.lastAcceptedConfiguration = s.lastAcceptedConfiguration ∧
s'.clusterUUIDKnown = s.clusterUUIDKnown ∧ s'.clusterUUIDCommitted = s.clusterUUIDCommitted) ∨
(s.term = 0 ∧ s.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
s.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧ s.clusterUUIDKnown = false ∧
s'.term = 0 ∧ s'.lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
s'.lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG)
/-- One step of the cluster. -/
inductive Step (P : Params) : Cluster V → Cluster V → Prop where
| bootstrap (W : Cluster V) (n : NodeId) (X : VotingConfiguration) (s : ClusterState V)
(cs' : CoordinationState V) (hX : P.initConfs X)
(hcontract : (W.node n).initialStateContract s)
(hconf : s.lastCommittedConfiguration = X ∧ s.lastAcceptedConfiguration = X)
(h : (W.node n).setInitialState s = .ok cs') :
Step P W (W.set n cs')
| startJoin (W : Cluster V) (n src : NodeId) (t : Nat) (cs' : CoordinationState V) (j : Join)
(hsrc : P.eligible src = true)
(h : (W.node n).handleStartJoin ⟨P.dn src, t⟩ = .ok (cs', j)) :
Step P W ((W.set n cs').send (.join j))
| join (W : Cluster V) (n : NodeId) (j : Join) (cs' : CoordinationState V) (b : Bool)
(hsent : W.sent (.join j)) (hdest : j.targetNode.id = n)
(h : (W.node n).handleJoin P.strategy j = .ok (cs', b)) :
Step P W (W.set n cs')
| clientValue (W : Cluster V) (n : NodeId) (s : ClusterState V) (cs' : CoordinationState V)
(p : PublishRequest V) (hcontract : (W.node n).clientValueContract s)
(h : (W.node n).handleClientValue s = .ok (cs', p)) :
Step P W ((W.set n cs').send (.publishRequest n p.acceptedState (W.node n).lastAcceptedTerm
(W.node n).lastAcceptedVersion))
| publish (W : Cluster V) (n src : NodeId) (s : ClusterState V) (pt : Nat) (pv : Int)
(cs' : CoordinationState V) (r : PublishResponse) (hsent : W.sent (.publishRequest src s pt pv))
(h : (W.node n).handlePublishRequest ⟨s⟩ = .ok (cs', r)) :
Step P W ((W.set n cs').send (.publishResponse n src r))
| respond (W : Cluster V) (n src : NodeId) (r : PublishResponse) (cs' : CoordinationState V)
(o : Option ApplyCommitRequest) (hsent : W.sent (.publishResponse src n r))
(h : (W.node n).handlePublishResponse (P.dn src) r = .ok (cs', o)) :
Step P W (match o with
| none => W.set n cs'
| some c => (W.set n cs').send (.applyCommit c))
| commit (W : Cluster V) (n : NodeId) (c : ApplyCommitRequest) (cs' : CoordinationState V)
(hsent : W.sent (.applyCommit c)) (h : (W.node n).handleCommit c = .ok cs') :
Step P W (W.set n cs')
| restart (W : Cluster V) (n : NodeId) (s' : ClusterState V) (hn : P.eligible n = true)
(hs : RestartState (W.node n).lastAcceptedState s') :
Step P W (W.set n (CoordinationState.init (W.node n).localNode (W.node n).currentTerm s'))
| restartAny (W : Cluster V) (n : NodeId) (t : Nat) (s' : ClusterState V) (hn : P.eligible n = false) :
Step P W (W.set n (CoordinationState.init (W.node n).localNode t s'))
/-- The clusters reachable from a fresh cluster. -/
inductive Reachable (P : Params) : Cluster V → Prop where
| init (W : Cluster V) : Initial P W → Reachable P W
| step (W W' : Cluster V) : Reachable P W → Step P W W' → Reachable P W'
/-- A (term, version) is committed when an `ApplyCommitRequest` for it has been sent (that it is then the key of a sent
publication follows from the invariant, `inv_committed_published`). -/
def Committed (W : Cluster V) (t : Nat) (v : Int) : Prop := ∃ src, W.sent (.applyCommit ⟨src, t, v⟩)
/-- `(t, v)` is the parent of `(t', v')`: a publication of `(t', v')` was made on top of an accepted `(t, v)`. -/
def Parent (W : Cluster V) (t : Nat) (v : Int) (t' : Nat) (v' : Int) : Prop :=
∃ src s, W.sent (.publishRequest src s t v) ∧ s.term = t' ∧ s.version = v'
/-- Descent between (term, version) pairs: the reflexive-transitive closure of `Parent` (reflexive on every pair,
published or not). -/
inductive Descends (W : Cluster V) : Nat → Int → Nat → Int → Prop where
| refl (t : Nat) (v : Int) : Descends W t v t v
| step (t : Nat) (v : Int) (t' : Nat) (v' : Int) (t'' : Nat) (v'' : Int) :
Descends W t v t' v' → Parent W t' v' t'' v'' → Descends W t v t'' v''
/-! ## The inductive invariant
Proof-side notions (none of them is used by the model above) and the invariant `Inv`, from which the safety theorems
follow. A publication is named by its *key*, its (term, version); its ghost parent is the key of the state its publisher
had accepted. Publications thus form a forest: following parents, versions strictly decrease until a term-0 key, the
*root*, which stands for a bootstrap state (several nodes may bootstrap, with different bootstrap configurations). All
notions are relations, never functions computed from the messages sent: `KeyLE` and `Below` compare keys, `Won` also
reads node states, and the others depend on the messages sent only. All sets of voters are lists of
cluster-manager-eligible nodes, so that `Params.InitCompatible` applies to them. -/
/-- The lexicographic order on (term, version) keys: `(t, v)` is at most `(t', v')`. -/
def KeyLE (t : Nat) (v : Int) (t' : Nat) (v' : Int) : Prop := t < t' ∨ (t = t' ∧ v ≤ v')
/-- The last accepted (term, version) `(lt, lv)` carried by a join is at or below the base `(bt, bv)` in the way
`handleJoin` compares them: an older term, or the same term and, unless that term is 0, a version at most `bv`.
(At term 0 a join carries a metadata version, `versionOrMetadataVersion`, which plays no role in safety.) -/
def Below (lt : Nat) (lv : Int) (bt : Nat) (bv : Int) : Prop := lt < bt ∨ (lt = bt ∧ (bt = 0 ∨ lv ≤ bv))
/-- A publication of term `t` and version `v` has been sent. -/
def Published (W : Cluster V) (t : Nat) (v : Int) : Prop :=
∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = t ∧ s.version = v
/-- The pair of configurations `(x, y)` (last committed, last accepted) *realizes* the key `(t, v)`: either `t = 0`
and `x = y` is a bootstrap configuration (a bootstrap state), or `(t, v)` is the key of a sent publication whose last
accepted configuration is `y` and whose last committed configuration is `x` — or, if `(t, v)` is committed, whose last
accepted configuration is also `x` (a node that applied the commit, `markCommitted`). The accepted state of every
bootstrapped cluster-manager-eligible node realizes its own key (`Inv.accepted_realizes`). -/
def Realizes (P : Params) (W : Cluster V) (t : Nat) (v : Int) (x y : VotingConfiguration) : Prop :=
(t = 0 ∧ x = y ∧ P.initConfs x) ∨
∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = t ∧ s.version = v ∧
y = s.lastAcceptedConfiguration ∧
(x = s.lastCommittedConfiguration ∨ (x = s.lastAcceptedConfiguration ∧ Committed W t v))
/-- Every member of `J` is a cluster-manager-eligible node that sent node `L` a join for term `t`. -/
def JoinVoters (P : Params) (W : Cluster V) (L : NodeId) (t : Nat) (J : List NodeId) : Prop :=
∀ x ∈ J, P.eligible x = true ∧
∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = x ∧ j.targetNode.id = L ∧ j.term = t
/-- Every member of `J` is a cluster-manager-eligible node that sent node `L` a join for term `t` whose last accepted
(term, version) is `Below` the base `(bt, bv)`. -/
def BaseVoters (P : Params) (W : Cluster V) (L : NodeId) (t bt : Nat) (bv : Int) (J : List NodeId) : Prop :=
∀ x ∈ J, P.eligible x = true ∧
∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = x ∧ j.targetNode.id = L ∧ j.term = t ∧
Below j.lastAcceptedTerm j.lastAcceptedVersion bt bv
/-- Every member of `A` is a cluster-manager-eligible node that sent a `PublishResponse` for term `t` and version
`v` (to any node). -/
def RespVoters (P : Params) (W : Cluster V) (t : Nat) (v : Int) (A : List NodeId) : Prop :=
∀ x ∈ A, P.eligible x = true ∧ ∃ d, W.sent (.publishResponse x d ⟨t, v⟩)
/-- An *election record* of node `L` for term `t`: the base `(bt, bv)` is of an older term, `(x, y)` realizes it, and
`J`, a quorum of both `x` and `y`, consists of eligible nodes that each sent `L` a term-`t` join with a last accepted
(term, version) `Below` the base. Both a node that has just won its election (its accepted state is the base) and the
first publication of a term (the publisher's state when it won) carry one. -/
def ElectionRecord (P : Params) (W : Cluster V) (L : NodeId) (t bt : Nat) (bv : Int) (x y : VotingConfiguration)
(J : List NodeId) : Prop :=
bt < t ∧ Realizes P W bt bv x y ∧ BaseVoters P W L t bt bv J ∧ x.hasQuorum J = true ∧ y.hasQuorum J = true
/-- Node `b` *won* term `t`: it is cluster-manager-eligible, and it has currently won the election of its current
term `t`, or it has sent a publication of term `t`. -/
def Won (P : Params) (W : Cluster V) (b : NodeId) (t : Nat) : Prop :=
P.eligible b = true ∧
(((W.node b).electionWon = true ∧ (W.node b).currentTerm = t) ∨
∃ s pt pv, W.sent (.publishRequest b s pt pv) ∧ s.term = t)
/-- The inductive invariant. Field names are descriptive; each docstring names the conjunct of the design it
transcribes (labels P*, C1, J*, R*, N*, L*, listed in `NOTES_OpenSearchSafety.md`). Node facts about the persisted
state hold for cluster-manager-eligible nodes only (a node that is not eligible may restart with any persisted state);
facts about the transient state hold for every node (a node that is not eligible never receives a join, so never holds
votes or wins). -/
structure Inv (P : Params) (W : Cluster V) : Prop where
-- Every node.
/-- Every node's `localNode` is its own `DiscoveryNode` `P.dn n`. -/
localNode_eq : ∀ n, (W.node n).localNode = P.dn n
/-- (N4) A node that has not won its election has last published version 0 and holds no publish votes. -/
idle_of_not_won : ∀ n, (W.node n).electionWon = false →
(W.node n).lastPublishedVersion = 0 ∧ (W.node n).publishVotes = VoteCollection.empty
/-- (N2) A node that has won its election has started a join since its last restart. -/
won_started : ∀ n, (W.node n).electionWon = true → (W.node n).startedJoinSinceLastReboot = true
/-- (N6) A node that holds join votes has started a join since its last restart. -/
votes_started : ∀ n, (W.node n).joinVotes.nodes ≠ [] → (W.node n).startedJoinSinceLastReboot = true
/-- (N10) A node that has started a join since its last restart is in a term ≥ 1. -/
started_term_pos : ∀ n, (W.node n).startedJoinSinceLastReboot = true → 1 ≤ (W.node n).currentTerm
/-- (N3) The join votes of a node that has won are a quorum of both its last committed and its last accepted
configuration. -/
won_quorum : ∀ n, (W.node n).electionWon = true →
(W.node n).joinVotes.isQuorum (W.node n).lastCommittedConfiguration = true ∧
(W.node n).joinVotes.isQuorum (W.node n).lastAcceptedConfiguration = true
/-- (N3r: for the default election strategy, the reverse half of `invariant()`'s second assertion; it omits the
strategy's additional constraint) The join votes of a node that has not won are not a quorum of both its last
committed and its last accepted configuration. -/
not_won_no_quorum : ∀ n, (W.node n).electionWon = false →
¬ ((W.node n).joinVotes.isQuorum (W.node n).lastCommittedConfiguration = true ∧
(W.node n).joinVotes.isQuorum (W.node n).lastAcceptedConfiguration = true)
/-- (N8) Every join vote node `n` holds is of an eligible node `m` that sent `n` a join for `n`'s current term, with
a last accepted (term, version) `Below` `n`'s last accepted (term, version). -/
joinVotes_sent : ∀ n m, m ∈ (W.node n).joinVotes.nodes → P.eligible m = true ∧
∃ j : Join, W.sent (.join j) ∧ j.sourceNode.id = m ∧ j.targetNode.id = n ∧
j.term = (W.node n).currentTerm ∧
Below j.lastAcceptedTerm j.lastAcceptedVersion (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion
/-- (N9) Every publish vote node `n` holds is of an eligible node `m` that sent `n` a `PublishResponse` for `n`'s
current term and last published version. -/
publishVotes_sent : ∀ n m, m ∈ (W.node n).publishVotes.nodes → P.eligible m = true ∧
W.sent (.publishResponse m n ⟨(W.node n).currentTerm, (W.node n).lastPublishedVersion⟩)
-- Cluster-manager-eligible nodes.
/-- (N1) The last accepted term of an eligible node is at most its current term. -/
term_le : ∀ n, P.eligible n = true → (W.node n).lastAcceptedTerm ≤ (W.node n).currentTerm
/-- (N7) The accepted state of an eligible node is either a never-bootstrapped term-0 state with empty
configurations, or its configurations `Realize` its key: a bootstrap state with a bootstrap configuration, or a sent
publication's term, version and configurations (the last committed one possibly replaced by the last accepted one,
if the publication is committed). Nothing else of the state (payload, metadata version, cluster-manager node,
cluster-UUID flags) is related to the publication, since a restart may rebuild it. -/
accepted_realizes : ∀ n, P.eligible n = true →
((W.node n).lastAcceptedTerm = 0 ∧
(W.node n).lastCommittedConfiguration = VotingConfiguration.EMPTY_CONFIG ∧
(W.node n).lastAcceptedConfiguration = VotingConfiguration.EMPTY_CONFIG) ∨
Realizes P W (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion
(W.node n).lastCommittedConfiguration (W.node n).lastAcceptedConfiguration
-- Joins and publish responses.
/-- Every join comes from the `DiscoveryNode` of its source and is addressed to an eligible node. -/
join_wf : ∀ j : Join, W.sent (.join j) →
j.sourceNode = P.dn j.sourceNode.id ∧ P.eligible j.targetNode.id = true
/-- (J1) An eligible node's joins are for terms at most its current term. -/
join_term_le : ∀ j : Join, W.sent (.join j) → P.eligible j.sourceNode.id = true →
j.term ≤ (W.node j.sourceNode.id).currentTerm
/-- (J2) An eligible node sends at most one join per term. -/
join_unique : ∀ j j' : Join, W.sent (.join j) → W.sent (.join j') → P.eligible j.sourceNode.id = true →
j.sourceNode.id = j'.sourceNode.id → j.term = j'.term → j = j'
/-- (J3) An eligible node's join for a term later than one of its publish responses carries a last accepted
(term, version) at least that of the response: it accepted before it voted. -/
join_after_response : ∀ (j : Join) (a d : NodeId) (r : PublishResponse), W.sent (.join j) →
W.sent (.publishResponse a d r) → j.sourceNode.id = a → P.eligible a = true → r.term < j.term →
KeyLE r.term r.version j.lastAcceptedTerm j.lastAcceptedVersion
/-- (R1) An eligible node's publish responses are for terms at most its current term, and for (term, version)s at
most its last accepted (term, version). -/
response_le : ∀ (a d : NodeId) (r : PublishResponse), W.sent (.publishResponse a d r) → P.eligible a = true →
r.term ≤ (W.node a).currentTerm ∧
KeyLE r.term r.version (W.node a).lastAcceptedTerm (W.node a).lastAcceptedVersion
/-- (R2) Every publish response answers a publication of its (term, version) sent by the node it is addressed to. -/
response_published : ∀ (a d : NodeId) (r : PublishResponse), W.sent (.publishResponse a d r) →
∃ s pt pv, W.sent (.publishRequest d s pt pv) ∧ s.term = r.term ∧ s.version = r.version
-- Publications.
/-- (P1) Every publication is sent by an eligible node, has term ≥ 1 (so the Zen1 branch of
`handlePublishRequest` is dead), a parent of at most its term and of a smaller version, and, if its parent is a
bootstrap state (term 0), a bootstrap configuration as last committed configuration. -/
pub_wf : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
P.eligible src = true ∧ 1 ≤ s.term ∧ pt ≤ s.term ∧ pv < s.version ∧
(pt = 0 → P.initConfs s.lastCommittedConfiguration)
/-- (P1, P5) The parent of a publication, if not a bootstrap state, is a publication (of key `(pt, pv)`), and the
configurations follow the reconfiguration discipline: the last committed configuration is the parent's, or, if the
parent is committed, the parent's last accepted one (reconfiguration rule R1); and the last accepted configuration
changes only if the last committed configuration is the parent's last accepted one (reconfiguration rule R2). -/
pub_parent : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → 1 ≤ pt →
∃ src' s' pt' pv', W.sent (.publishRequest src' s' pt' pv') ∧ s'.term = pt ∧ s'.version = pv ∧
(s.lastCommittedConfiguration = s'.lastCommittedConfiguration ∨
(s.lastCommittedConfiguration = s'.lastAcceptedConfiguration ∧ Committed W pt pv)) ∧
(s.lastAcceptedConfiguration ≠ s'.lastAcceptedConfiguration →
s.lastCommittedConfiguration = s'.lastAcceptedConfiguration)
/-- (P2) Two publications with the same key are the same message (source, state and parent). -/
pub_unique : ∀ src s pt pv src' s' pt' pv', W.sent (.publishRequest src s pt pv) →
W.sent (.publishRequest src' s' pt' pv') → s.term = s'.term → s.version = s'.version →
src = src' ∧ s = s' ∧ pt = pt' ∧ pv = pv'
/-- Every publication descends from a root (a term-0 key): the chain of its ancestors is finite. -/
pub_rooted : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → ∃ v₀, Descends W 0 v₀ s.term s.version
/-- (P4) Two publications of the same term are related by descent. -/
pub_same_term : ∀ src s pt pv src' s' pt' pv', W.sent (.publishRequest src s pt pv) →
W.sent (.publishRequest src' s' pt' pv') → s.term = s'.term →
Descends W s.term s.version s'.term s'.version ∨ Descends W s'.term s'.version s.term s.version
/-- (P6) The eligible nodes that sent the publisher a join for the publication's term include a quorum of both of
the publication's configurations. -/
pub_voters : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
∃ J, JoinVoters P W src s.term J ∧ s.lastCommittedConfiguration.hasQuorum J = true ∧
s.lastAcceptedConfiguration.hasQuorum J = true
/-- (P7) The first publication of a term (its parent is of an older term) carries the election record of its
publisher: the parent key, realized by the publication's last committed configuration and some `y` (the parent's
last accepted configuration), with a quorum of joins `Below` the parent. -/
pub_election : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) → pt < s.term →
∃ y J, ElectionRecord P W src s.term pt pv s.lastCommittedConfiguration y J
-- Commits.
/-- (C1, with the weakening forced by `handleCommit` at a leader, D1) Every commit is of a sent publication whose
publish responses from eligible nodes include a quorum `A` of its last accepted configuration and either of its last
committed configuration, or (D1) its parent is committed and has the same last accepted configuration. -/
commit_quorum : ∀ c : ApplyCommitRequest, W.sent (.applyCommit c) →
∃ src s pt pv, W.sent (.publishRequest src s pt pv) ∧ s.term = c.term ∧ s.version = c.version ∧
∃ A, RespVoters P W c.term c.version A ∧ s.lastAcceptedConfiguration.hasQuorum A = true ∧
(s.lastCommittedConfiguration.hasQuorum A = true ∨
(Committed W pt pv ∧ ∃ src' s' pt' pv', W.sent (.publishRequest src' s' pt' pv') ∧ s'.term = pt ∧
s'.version = pv ∧ s'.lastAcceptedConfiguration = s.lastAcceptedConfiguration))
-- Leaders.
/-- (L1) For each term `t`, at most one node `b` has `Won P W b t`. -/
won_unique : ∀ a b t, Won P W a t → Won P W b t → a = b
/-- (L2) A node that published in a term is past that term, or still in it and either still elected or restarted
since (so it cannot win that term again). -/
pub_source_term : ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
s.term < (W.node src).currentTerm ∨
(s.term = (W.node src).currentTerm ∧
((W.node src).electionWon = true ∨ (W.node src).startedJoinSinceLastReboot = false))
/-- (L3) Every publication of an elected node's current term, whoever sent it, has a version at most the node's last
published version, (current term, last published version) descends from it, and the node's join votes are a quorum
of both of its configurations. -/
leader_pubs : ∀ n, (W.node n).electionWon = true → ∀ src s pt pv, W.sent (.publishRequest src s pt pv) →
s.term = (W.node n).currentTerm →
s.version ≤ (W.node n).lastPublishedVersion ∧
Descends W s.term s.version (W.node n).currentTerm (W.node n).lastPublishedVersion ∧
(W.node n).joinVotes.isQuorum s.lastCommittedConfiguration = true ∧
(W.node n).joinVotes.isQuorum s.lastAcceptedConfiguration = true
/-- (L4) An elected node with a publication in flight (last published version ≠ last accepted version) sent it on
top of its current accepted key; its last published configuration is that publication's last accepted one; and its
last committed configuration is the publication's, or (D1: the node applied the commit of its accepted state) the
publication's last accepted configuration, its accepted state being committed with that same last accepted
configuration. -/
leader_inflight : ∀ n, (W.node n).electionWon = true →
(W.node n).lastPublishedVersion ≠ (W.node n).lastAcceptedVersion →
∃ s, W.sent (.publishRequest n s (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion) ∧
s.term = (W.node n).currentTerm ∧ s.version = (W.node n).lastPublishedVersion ∧
(W.node n).lastPublishedConfiguration = s.lastAcceptedConfiguration ∧
((W.node n).lastCommittedConfiguration = s.lastCommittedConfiguration ∨
((W.node n).lastCommittedConfiguration = s.lastAcceptedConfiguration ∧
Committed W (W.node n).lastAcceptedTerm (W.node n).lastAcceptedVersion ∧
(W.node n).lastAcceptedConfiguration = s.lastAcceptedConfiguration))
/-- (L5) An elected node with no publication in flight has either accepted a publication of its term (and its last
published configuration is its last accepted one), or has an accepted state of an older term and no publication of
its term exists. -/
leader_settled : ∀ n, (W.node n).electionWon = true →
(W.node n).lastPublishedVersion = (W.node n).lastAcceptedVersion →
((W.node n).lastAcceptedTerm = (W.node n).currentTerm ∧
(W.node n).lastPublishedConfiguration = (W.node n).lastAcceptedConfiguration) ∨
((W.node n).lastAcceptedTerm < (W.node n).currentTerm ∧
∀ src s pt pv, W.sent (.publishRequest src s pt pv) → s.term ≠ (W.node n).currentTerm)
end OpenSearchSafety
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_OpenSearchSafety.lean
This file imports Definitions.Def_OpenSearchCoordination and introduces, in the namespace OpenSearchSafety (with OpenSearchCoordination opened), 25 declarations, in this order: the message type Message; the parameters Params, with Params.dn and the condition Params.InitCompatible; the predicate BootstrapConfig; the cluster type Cluster with the updates Cluster.set and Cluster.send; Initial, RestartState, the step relation Step and Reachable (together, the model); the relations Committed, Parent and Descends on (term, version) pairs; and, under the heading "The inductive invariant", the proof-side notions KeyLE, Below, Published, Realizes, JoinVoters, BaseVoters, RespVoters, ElectionRecord, Won and the 30-field invariant Inv. The imported notions are expanded first so that each declaration can be read on its own. Java line citations were checked against the local OpenSearch checkout, whose HEAD is the cited revision b2a54ba5c0defba3d1d20423e911d4bf920bab19.
Imported notions, expanded
Node ids and discovery nodes. A node id is a natural number (Java: a string; only equality is used). A discovery node is a pair (id , cluster-manager flag ); two discovery nodes are equal iff both components are equal. .
Voting configurations. A voting configuration is a list of node ids together with a proof that the list is strictly increasing. It therefore has no duplicates, and two configurations are equal iff their lists are equal, i.e. iff they contain the same ids. is the configuration with the empty list; is empty iff its list is empty. For a list of node ids,
the count ranging over the (duplicate-free) members of : strictly more than half of the members of occur in . Members of outside , the order of and repetitions in are irrelevant, and has no quorum (not even of , since fails). Below, " is a quorum of " means .
Vote collections. A vote collection is a list of node ids (most recent first); the empty collection is . For a discovery node , is if 's cluster-manager flag is true and , and otherwise; so a vote from a node whose flag is false is never recorded, and a node is recorded at most once. A collection is a quorum of iff ; it contains a vote for iff ; it is empty iff .
Cluster states. A cluster state over a payload type has nine fields: ; ; ; configurations (last committed) and (last accepted); , the cluster-manager node, which is "none" or "some " with ; Booleans and ; and a payload . Its key is the pair . ("version or metadata version") is if and otherwise. is with replaced by (no change if they are already equal) and then, if is true and is false, set to true; every other field is unchanged.
Message payloads. A start-join request is a pair (source discovery node, term ). A join consists of a source discovery node , a target discovery node , a term , a last accepted term and a last accepted version ; equality of joins is equality of all five fields. A publish request wraps one cluster state. A publish response is a pair . An apply-commit request is a triple (source discovery node, term , version ).
Election strategies. An election strategy is a single Boolean function of a discovery node, a current term, an accepted term, an accepted version, two configurations and a vote collection. The default strategy returns true on every input. (ElectionStrategy.Monotone is defined in the imported file and not used in this one.)
Coordination states. A coordination state has nine fields: , a discovery node; the persisted part and (the last accepted cluster state); and the transient part , ("started a join since the last reboot"), ("election won"), (last published version), (last published configuration) and . Derived: , , , . The constructor is the coordination state with local node , current term , accepted state , empty join votes, , , and empty publish votes.
holds iff is a quorum of , is a quorum of , and is true. holds iff is a quorum of and of .
The handlers return either an error or a result; the cluster steps below use only successful calls ("succeeds with"). Guards are tested in the order listed, and the first guard that applies produces the error.
- : error if is non-empty; otherwise succeeds with with . Its contract (Java assertions, not checked by the handler) is the conjunction: ; empty; ; empty; ; empty; empty; ; ; non-empty; non-empty.
- : error if ; otherwise succeeds with the pair of ( with , , , , , , ) and the join . The accepted state is unchanged.
- : (1) error if ; (2) error if is false; (3) error if ; (4) error if and ; (5) error if is empty; otherwise, with and (evaluated on 's own terms and configurations, which the call does not change), succeeds with , where is with and , and in addition when is true and was false. The target of is not checked (Java asserts it), and nothing prevents from going from true to false (Java only asserts that it cannot).
- : (1) error if is false; (2) error if ; (3) error if ; (4) error if ; (5) error if and ; (6) error if is not a quorum of ; otherwise succeeds with ( with , , ; the publish request of ). Its contract is .
- : (1) error if ; (2) else, if and : when , error if is none, accept if and "some " differs from , error otherwise; when , error; (3) otherwise accept. Accept means: succeed with ( with ; the response ). Transient fields are unchanged.
- : (1) error if is false; (2) error if ; (3) error if ; otherwise, with the first component of and equal to with , succeeds with if is a quorum of and of , and with otherwise.
- : (1) error if ; (2) error if ; (3) error if ; otherwise succeeds with with .
(javaInvariant is defined in the imported file and not used in this one.)
Citation check of the imported transcription. The handlers above, the constructor (CS:84-106), isElectionQuorum (CS:144-154 with ES:68-88), isPublishQuorum (CS:156-158), VoteCollection.addVote (CS:755-757; handleJoin calls addJoinVote, CS:759-765, which calls addVote and only additionally records the join), VotingConfiguration.hasQuorum, isEmpty and EMPTY_CONFIG (CM:405-409, 433-435, 385), getVersionOrMetadataVersion (CLS:239-244), markLastAcceptedStateAsCommitted with commitVotingConfiguration (CS:703-740) and ZEN1_BWC_TERM (Coordinator.java:134) were compared with the cited lines and match, guards and their order included, up to the abstractions the imported file declares (remote persisted state omitted, Java assertions turned into contracts, a null incoming cluster-manager in the Zen1 branch treated as a rejection).
Declaration 1: Message
Message V is an inductive type with four constructors; messages are equal iff they have the same constructor and equal arguments (for publish requests this includes the whole cluster state, payload included).
join j, for a join .publishRequest src s pt pv, written : a source node id , a cluster state , and , , the ghost parent (term, version) (docstring: "with the ghost parent"). A publish request has no addressee.publishResponse src dest r, written for : a response from node id to node id .applyCommit c, written for ; the source is a discovery node. It has no addressee.
Start-join requests are not messages of the model.
Declaration 2: Params
A structure with three fields: (docstring: DiscoveryNode.isClusterManagerNode() of each node; it is fixed for the whole execution); , an arbitrary predicate on voting configurations, "the configurations a node may bootstrap with" (it may be empty, a single configuration, or infinitely many); and , one election strategy used by every node. Below, abbreviates (" is eligible").
Declaration 3: Params.dn
is the discovery node .
Declaration 4: Params.InitCompatible
is the proposition: for all configurations with and , and all lists of node ids all of whose members are eligible,
is included, but for the implication holds automatically (two sets of members of , each of more than half its size, intersect), so the condition constrains only pairs of distinct bootstrap configurations. It holds trivially when has at most one element. A configuration with no eligible member has no eligible quorum and so imposes nothing. The docstring ("votes of cluster-manager-eligible nodes that form a quorum of one bootstrap configuration share a voter with votes that form a quorum of another") matches. This condition is not used by the model; it appears only as a hypothesis of theorems.
Declaration 5: BootstrapConfig
For , functions , and a configuration , is the conjunction of
- for every node id : ;
- .
So is exactly the set of the contributions (requirement contributes if matched and otherwise), and strictly more than half of the requirement indices are matched; in particular . Left unconstrained: and need not be injective and their images need not be disjoint, so may have fewer than members and the matched count need not equal the number of distinct resolved ids; nothing is said about the eligibility of any id; nothing requires the bootstrapping node to be among the resolved ids. This predicate is not referenced by any other declaration of the file; in particular the bootstrap step uses , and nothing in this file links the two.
Citation check. CBS:176-215 (onFoundPeersUpdated) bootstraps only if nodesMatchingRequirements.size() * 2 > bootstrapRequirements.size(); CBS:259-273 (startBootstrap) forms the configuration from the ids of the matching nodes and "{bootstrap-placeholder}-" + requirement for each unsatisfied requirement; CBS:306-335 (checkRequirements) cancels bootstrapping if a requirement matches several nodes or a node matches several requirements. The Lean predicate matches the counting and the shape of the configuration. The Java code additionally requires the local node to be cluster-manager-eligible and among the matching nodes (CBS:179, 202-209) and guarantees the injectivity that the Lean leaves open; Java's best-effort bootstrap without configured requirements (scheduleUnconfiguredBootstrap, CBS:217-250) is not described by this predicate.
Declaration 6: Cluster
Cluster V is a structure with two fields: coordination states (one for every natural number), and , a predicate on messages ("has been sent"). For an arbitrary cluster, is an arbitrary, possibly infinite, set of messages.
Declaration 7: Cluster.set
is with node 's state replaced by : its node function maps to if and to otherwise; is unchanged.
Declaration 8: Cluster.send
is with replaced by ; the node states are unchanged.
Declaration 9: Initial
is the conjunction of
- for every node there is a cluster state with , , and ;
- no message has been sent: .
So every node (eligible or not) has local node , current term , an accepted state of term with empty configurations, no votes, , and . The state may differ from node to node, and its version, metadata version, cluster-manager node, both cluster-UUID flags and payload are unconstrained. The docstring lists only "version, metadata version and payload" as arbitrary; the cluster-manager node and the UUID flags (so a fresh node may have uuidKnown = true, even uuidCommitted = true) are left free as well.
Declaration 10: RestartState
For cluster states (the accepted state before the restart) and (after), is the disjunction of
- (persisted state) , , , , and — the metadata version, the cluster-manager node and the payload of are free;
- (remote-store restore) , , , and , — everything else of (version, metadata version, cluster-manager node, UUID flags, payload) is free.
The docstring matches. Citation check. GatewayMetaState.java:164-197 builds the restarted node's state from the on-disk metadata (which carries the coordination metadata — term and both configurations — and the cluster UUID with its committed flag) and the persisted version, then rebuilds the rest (prepareInitialClusterState); this supports branch 1 (the metadata version is also left free in Lean, which only adds behaviours; the module docstring mentions only the payload and the cluster-manager node as rebuilt). The remote-store restore is GatewayMetaState.java:169-188 (the cited 166-185 is off by a few lines): it is attempted when the node is cluster-manager-eligible, remote cluster state is enabled, the locally loaded cluster UUID is unknown, and the remote store knows a last cluster UUID; the restore starts from Metadata.EMPTY_METADATA (GatewayMetaState.java:293-299) and copies back only index metadata, persistent settings, templates, customs and the version (RemoteStoreRestoreService.java:218-267, 279-307), so the coordination metadata stays empty (term 0, empty configurations) while the version is taken from the remote state. Lean's branch 2 has this result but a narrower trigger: Java tests only that the cluster UUID is unknown, whereas Lean also requires the old state to have term 0 and empty configurations. In the Lean model the UUID flags are otherwise unconstrained (bootstrap and client-value states may carry uuidKnown = false at term or with non-empty configurations), so for such states the Lean restart relation omits a Java restore behaviour; whether such states occur in Java (where bootstrapping generates a UUID) is outside the model.
Declaration 11: Step
is an inductive relation with nine cases. In each case is with exactly one node's state replaced (via set) and possibly one message added (via send); no case removes a message. Write for the acting node's state before the step.
bootstrap(node , configuration , cluster state , coordination state ): if , , , and succeeds with , then . Unfolded: has accepted term , empty last committed and last accepted configurations, , empty , has not won and holds no votes; has term , version , and both configurations equal to the non-empty bootstrap configuration ; is with accepted state (current term and transient fields unchanged, so stays empty). The metadata version, cluster-manager node, UUID flags and payload of are free. Not required: that be eligible, that , or any quorum of discovered nodes (Java'ssetInitialConfiguration, CO:1101-1161, checks all three and throws otherwise). No message is sent. Several nodes may bootstrap, with different configurations.startJoin(nodes , , term , , join ): if and succeeds with , then . Unfolded: ; has current term , , , , not won, no votes, same accepted state; . Any node, eligible or not, may do this at any time, for any eligible requester (itself included) and any larger term.join(node , join , , Boolean ): if has been sent, , and succeeds with , then . ( is unused.)clientValue(node , cluster state , , publish request ): if (i.e. ) and succeeds with , then . Since , the message is : its ghost parent is the publisher's accepted key at that moment. Unfolded conditions: ; ; ; ; or ; is a quorum of ; . The rest of is free. is with , , no publish votes.publish(nodes , , state , , , , response ): if has been sent and succeeds with , then . Any node (the publisher itself, an ineligible node, a node never bootstrapped) may handle any sent publish request, any number of times; the ghost parent plays no role; and is with accepted state .respond(nodes , , response , , optional apply-commit ): if has been sent (addressed to ) and succeeds with , then if is none and if is some apply-commit. The voter added is , so an ineligible responder is never counted; the apply-commit, when produced, is .commit(node , apply-commit , ): if has been sent and succeeds with , then . Any node may handle any sent apply-commit.restart(node , state ): if and , then : same local node and current term, accepted state , transient part reset ().restartAny(node , term , state ): if , then , for any (possibly smaller than before) and any .
A message's presence in is the only condition on it, and never shrinks, so a sent message can be handled any number of times, or never.
Declaration 12: Reachable
is the least predicate on clusters that contains every with and contains whenever it contains and .
Declaration 13: Committed
, the source ranging over all discovery nodes. The docstring speaks of "a published state (term, version)", but the definition does not require to be the key of any publication.
Declaration 14: Parent
: some publication of key has ghost parent . A key may have several parents if several publications share its key (excluded by Inv field 20, not by this definition).
Declaration 15: Descends
is the least relation on pairs of keys with (refl) for every , and (step) . Writing for — the first key is the ancestor — this holds iff there is a chain , , with for every . The docstring says "descent between published (term, version) pairs", but reflexivity holds for every pair, published or not; a pair that is not the key of a publication has no ancestor but itself. For an arbitrary the relation may have cycles; acyclicity comes only from Inv.
Declaration 16: KeyLE
: the lexicographic order on keys.
Declaration 17: Below
: lexicographic, except that when both terms are the versions are not compared. handleJoin accepts a join at a node (as far as guards 3 and 4 go) iff ; for this is exactly , and for Below is weaker (it drops the comparison with the metadata version). The docstring says this.
Declaration 18: Published
. It is not used by any other declaration of this file.
Declaration 19: Realizes
For a key and configurations (in the role of a last committed configuration) and (last accepted), is the disjunction of
- — the version is then unconstrained;
- there is a sent with key , , and either , or and .
The docstring matches; its last sentence (that eligible bootstrapped nodes realize their own key) is a claim made by Inv field 11, not by this definition.
Declarations 20–22: JoinVoters, BaseVoters, RespVoters
For a list (or ) of node ids:
- : every has and there is a sent with , and .
- : the same, with in addition for that join.
- : every has and has been sent for some — the destination is arbitrary.
All three hold vacuously for the empty list and allow repetitions. Docstrings match.
Declaration 23: ElectionRecord
. The pair is called the base. Since is a quorum of , both and are non-empty. Nothing requires to have won, to be eligible (although, under Inv field 12, the target of a sent join is eligible) or to have published, nor the base to be published (it may be a term-0 key). The docstring's second sentence (that a node that has just won, and the first publication of a term, carry a record) is a claim about other notions, not part of the definition.
Declaration 24: Won
. A node that has published in term satisfies forever, whatever its later state. The docstring matches.
Declaration 25: Inv
is a structure of 30 propositional fields, i.e. their conjunction. Notation: for a node let and write , , for , , , , , and , for the node-id lists of 's join and publish votes; "sent" means in ; node variables range over all of .
Every node :
localNode_eq: .idle_of_not_won(N4): . The docstring's "has published nothing in its term" is stronger than the term, which constrains only the local variables: a node that published in its term and then restarted has although its publication is in .won_started(N2): .votes_started(N6): .started_term_pos(N10): .won_quorum(N3): is a quorum of and a quorum of .not_won_no_quorum(N3r): is a quorum of and of . The docstring calls this "the reverse half ofinvariant()". Java'sinvariant()assertselectionWon == isElectionQuorum(joinVotes), whose reverse half also includes the strategy's additional constraint; the field omits it and is therefore stronger, coinciding with Java's reverse half only when the strategy's constraint is always true (for instance the default strategy).Invnever mentions .joinVotes_sent(N8): for every : , and some sent has , , and .publishVotes_sent(N9): for every : and has been sent.
Every eligible node :
term_le(N1): .accepted_realizes(N7): .
Joins and publish responses:
join_wf: every sent has and .join_term_le(J1): every sent with has .join_unique(J2): any two sent joins with , and are equal (all five fields, in particular the same target).join_after_response(J3): for every sent and sent with , and : .response_le(R1): for every sent with : and .response_published(R2): for every sent (no eligibility condition) there is a sent from with key .
Publications (for every sent ):
pub_wf(P1): , , , , and .pub_parent(P1, P5): if , there is a sent with key such that (a) , or ( and ); and (b) .pub_unique(P2): any two sent publications with the same key are the same message: same source, same cluster state (all nine fields), same parent.pub_rooted: . (The docstring's gloss "the chain of its ancestors is finite" is an interpretation; the term asserts a finite parent chain from some term-0 key.)pub_same_term(P4): for every other sent with : or the converse.pub_voters(P6): there is a list with that is a quorum of and of .pub_election(P7): if , there are a configuration and a list with .
Commits:
commit_quorum(C1, D1): for every sent there are a sent with key and a list with , a quorum of , and either a quorum of , or ( and some sent with key has ).
Leaders:
won_unique(L1): .pub_source_term(L2): for every sent : , or and ( or ).leader_pubs(L3): if , then every sent with — from any source — has , , and a quorum of and of . (The docstring says "an elected node's publications of its term"; the term covers all publications of that term.)leader_inflight(L4): if and , there is a state with sent, , , , and either , or (, and ).leader_settled(L5): if and : either ( and ), or ( and no sent publication has term ).
Docstrings of the remaining fields match their terms. Labels: localNode_eq, join_wf and pub_rooted carry none; "R1"/"R2" name both fields 16/17 and the two clauses (a)/(b) of field 19 in its docstring; "P1" names fields 18 and 19. The structure docstring's split — persisted facts for eligible nodes only, transient facts for every node — holds with the nuance that some every-node fields (5–8) mention persisted components, under a transient premise.
Satisfiability. Every Initial cluster satisfies all 30 fields: fields 1, 2, 10 and 11 by direct check, field 7 because has no quorum, the others vacuously (no message sent, no node won, started or holding votes). So Inv is not contradictory. Its preservation by Step is not part of this file.
The module and section docstrings
- The network description ("a message, once sent, stays available forever and may be handled any number of times, by any node it is addressed to, or never") matches
Step: joins are handled only by their target id, responses only by their destination, publish requests and apply-commits by any node. - "Each step is a successful call of one
CoordinationStatemethod, its output, if any, being sent" matches;restart/restartAnycall the constructor. "The steps cover every call theCoordinatormakes … theCoordinator's own guards only reject more" was checked only for the one cited method, CO:1101-1161 (Coordinator.setInitialConfiguration), whose extra guards (eligible local node, local node in the configuration, quorum of discovered nodes) are indeed absent from the Lean step; the bullet attributes it toClusterBootstrapService, which calls it. - "nodes may bootstrap with different configurations (see
BootstrapConfig)": the step uses ;BootstrapConfigis not connected to it in this file. - The
restartbullet matches branch 1 andrestartAny; for the remote-store branch see Declaration 10 (narrower trigger than Java's). GatewayMetaState.java:164-197 and the use ofLucenePersistedStatefor cluster-manager nodes (line 200) versusAsyncLucenePersistedState(lines 202-206) orInMemoryPersistedState(line 255) for others match the description. - The assumption citing GatewayMetaState.java:232-255 matches: a node started with neither the cluster-manager nor the data role writes term 0 and an empty state to disk.
CoordinationStateTestCluster(test/framework,invariant()at lines 331-370) checks one cluster-manager per term and one state per (term, version) over all publish requests, after random runs in which messages are never removed, start-join terms are occasionally random, elected nodes occasionally publish random terms, versions and configurations, and nodes reboot (also toggling the cluster-manager role, and resetting ineligible nodes' state). The docstring's "the first two safety properties" refers to a list not present in this file.- Section docstring: "Publications thus form a forest: following parents, versions strictly decrease until a term-0 key" is a consequence of
Inv(fields 18, 20, 21), not of the definitions, which allow arbitrary .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.