cluster raft: two leaders can be elected in the same term

[fabracht]

Two nodes can be Raft leader in the same term (election safety violation). On a fresh 5-node start the second leader issues its own partition assignments, and the nodes then report different partition maps for minutes.

Evidence

Fresh 5-node cluster (cluster start, nodes started 0.5 s apart, partial-mesh --peers), polling $SYS/mqdb/cluster/status on every node every 2 s. One captured run on main (abcaf6c) with mqdb_cluster::cluster::raft::coordinator=debug:

n1 19:52:40.929 became Raft leader node=1                        (term 1)
n2 19:52:41.902 sending RequestVote to=1 term=1                  (48 ms after n2 started)
n2 19:52:43.462 received AppendEntries from=1 term=1 entries=40 prev_log_index=257
n2 19:52:43.486 became Raft follower node=2 leader=Some(1)
n5 19:52:43.543 sending RequestVote to=1..4 term=1               (85 ms after n5 started)
n2 19:52:43.559 responding to RequestVote granted=true
n3 19:52:43.559 responding to RequestVote granted=true
n4 19:52:43.559 responding to RequestVote granted=true
n5 19:52:43.570 became Raft leader node=5                        (term 1)
n1 19:52:43.995 sending AppendEntries to=2 term=1 entries=128    (n1 still leading term 1)
n1 19:52:44.512 sending AppendEntries to=2 term=1 entries=208

Both then found unique-constraint voters with term=1.

Cause

1. RaftState::become_follower clears voted_for even when the term does not change (cluster/raft/state.rs, self.voted_for = None). Node 2 voted for itself in term 1, then became a follower of node 1 in term 1 and forgot that vote, so it could vote again in term 1. Nodes 3 and 4 did the same. Raft only resets the vote when the term increases.
2. A joining node starts an election on its first tick. last_heartbeat_time starts at 0, so now >= last_heartbeat_time + election_timeout is already true, and can_start_election returns true at once when peers are configured (they are added from --peers at startup, cluster_agent/init.rs). Every joiner campaigned in term 1 within 26–85 ms of starting, before hearing from the existing leader.
3. Node 2's log was empty (it had rejected node 1's first AppendEntries on prev_log_index mismatch), so node 5's empty log passed the up-to-date check.

Contributing: node 1 sent its first AppendEntries to the new peers 2.5 s after becoming leader and applied about one partition command per 10 ms, which leaves a long window for 1–3.

Frequency (16 fresh starts each, 180 s each, settled = all nodes report the same complete map with every node holding primaries for 3 consecutive polls)

	second election	never settled within 180 s
#139 (3c94ea5)	1/16	1/16
main (abcaf6c)	10/16	8/16

Fisher exact p = 0.002 and 0.016. Every never-settled run had a second election. The faulty Raft code predates #145–#151; which of those changes raises the frequency is not yet established.

Possibly related: #153 (a record missing on the new primary after its partition moved). Not verified.

Plan

TLA+ model of election with same-term step-down and first-tick elections (expect a two-leaders-in-one-term counterexample), then fix both defects, then verify with the same 16-run settle measurement on 5 nodes (expect 0 never-settled), then bisect #145–#151 with the settle method.

[fabracht]

Correction: the frequency table above is wrong. The harness that produced it built each node's --peers with seq 1 $((n-1)), which on macOS prints 1 0 for node 1. Node 1 was therefore started with itself and a nonexistent node 0 as peers. The real tools (mqdb dev start-cluster, the dev test suites) build the list from a Rust range and give node 1 no peers.

Re-measured with the harness fixed. 16 fresh 5-node starts each, polling every node's status every 2 s for 120 s. "Split" means a second Raft election and nodes reporting different partition maps for the rest of the run.

configuration	split	time to settle
partial mesh (node n peers with 1..n-1, as the dev tooling does), #139 (3c94ea5)	0/16	median 32 s, max 64 s
partial mesh, main (abcaf6c)	2/16	median 64 s; 2 never settled
full mesh (every node peers with all others, as the README requires), main	0/16	8–9 s every run

The base-vs-main difference in splits (0/16 vs 2/16) is not significant (Fisher p ≈ 0.48). The difference in settle time is (Mann–Whitney p ≈ 0.014); its cause in #145–#151 is not identified yet.

What the split needs

Traced in a correctly configured partial-mesh run (main, run 6) with Raft debug logging. It takes four defects together:

• D3: the startup grace period never applies. RaftCoordinator construction calls self.node.tick(0) (raft/coordinator/mod.rs, rebuild_partition_map), so startup_time = 0 and later wall-clock ticks are past the 10 s grace at once. A node with no peers elects itself immediately: node 1 led 10 ms after its Raft task started.
• D4: quorum is counted over each node's own peer list, which starts as the configured --peers and grows through add_peer. Node 1, with no peers, won term 1 with a quorum of 1.
• D2: a new node's election timer starts expired. last_heartbeat_time starts at 0, so every joiner campaigned in term 1 within 26–85 ms of starting.
• D1: become_follower clears voted_for on a same-term step-down (raft/state.rs). Nodes 2–4 each voted for themselves in term 1, stepped down on node 1's term-1 AppendEntries, then granted node 5's term-1 request. Node 5 became leader in term 1 while node 1 kept sending term-1 AppendEntries.

D1 alone cannot produce two leaders in a static full mesh. A term-t leader's majority voted for it, and D1 only resets the votes of candidates that had voted for themselves, so a second leader would need a majority among the remaining nodes. The membership defects (D3, D4) are what let node 1 lead with a quorum of 1. This matches the full-mesh row: 0/16.

specs/RaftElectionSafety.tla (in progress) finds two leaders in one term in 8 steps in the partial-mesh topology even with D1 fixed, through the D4 path.

Exposure

• The dev tooling uses the partial mesh: mqdb dev start-cluster's default topology, and the clusters the ownership and sharing suites start themselves. Those suites have been running on a configuration prone to this.
• Adding a node to a running cluster is a membership change of the same kind, because the existing nodes do not list it. Not yet measured.

[fabracht]

Fixed by #158 (958122e): same-term step-down keeps the vote, the election timer starts on the first tick with a randomized first timeout, and the startup grace applies again. On 5 nodes with partial peer lists, 16/16 fresh starts now settle with one leader (2/16 split before). The remaining defect, quorum computed over each node's own peer list with no committed membership, is tracked in #157.