阅读中文版本

Build a Leader Election via Bully

A bully algorithm leader election where the highest-id live node becomes leader, detecting coordinator failure and starting an election with O(n^2) messages in the worst case.

leader-election-bully/
├── src/election.ts
├── src/heartbeat.ts
├── src/leader.ts
├── tests/election.test.ts
└── package.json

if (now - lastLeaderHeartbeat > TIMEOUT) startElection();

const higher = members.filter(m => m.id > self.id); if (higher.length === 0) declareLeader();

onElection(() => { respond(); startElection(); });

for (const m of members) send(m, {type:"coordinator", leader: self.id});

Project overview

A cluster without a leader cannot make coordinated decisions, and a cluster with two leaders makes conflicting ones. A leader election picks one, and the bully algorithm picks the highest-id live node, which is deterministic and easy to reason about. The highest id wins because it bullies the lower ids, not because it is the best, which is why the algorithm is named.

The election starts when a node detects the leader is dead. The node sends an election message to all higher-id nodes, because one of them should be the leader. If none respond, the node is the highest live node, and it declares itself leader. If a higher-id node responds, it starts its own election, and the original node waits. The escalation ensures the highest live node wins.

The coordinator message ends the election. The new leader sends a coordinator message to all nodes, which accept it as the leader. The message is the authority, not the election itself, because the election is a process, not a result, and the coordinator message is the result.

The heartbeat is what detects the leader failure. The leader sends a heartbeat on a schedule, and a node that misses it for a timeout starts an election. The timeout is a trade-off: too short and a slow leader triggers false elections; too long and a dead leader is not replaced quickly.

The value of this project is the escalation, not the election. Sending messages is trivial; ensuring the highest live node wins, not just the node that started the election, is the part worth learning, because that is what makes the bully algorithm correct, not just fast.

What you will build

The project delivers five capabilities, each driven by a test:

• Highest-id wins
• Failure detection via heartbeat
• Election message flooding
• Coordinator announcement
• Split-brain prevention via quorum

Each node has a unique id and knows the cluster membership. A node that detects the leader dead sends an election message to all higher-id nodes; if none respond, it declares itself leader and announces to all. A higher-id node that receives an election message responds and starts its own election. A heartbeat detects leader failure; a quorum prevents split-brain.

Architecture and data model

Each node has a unique id, typically an integer or a string that is totally ordered. The membership is the set of all node ids and addresses, known to every node. The algorithm assumes static membership: adding a node requires a restart, because the membership is not gossiped.

The election message is sent to all higher-id nodes. The message is a type byte and the sender id. A higher-id node that receives it responds with an ok message and starts its own election. The response tells the sender that a higher node is alive, so the sender should not declare itself leader. The escalation from the higher node ensures the highest live node eventually starts an election with no higher live nodes and wins.

The declare-leader step happens when a node sends an election message and receives no responses within a timeout. The node is the highest live node, because every higher-id node is dead or partitioned. It sends a coordinator message to all nodes, which accept it as the leader and stop their own elections.

The heartbeat is a periodic message from the leader to all nodes. A node that misses the heartbeat for a timeout starts an election. The heartbeat is the failure detector, and the timeout is the trade-off between false failure and slow detection.

The quorum is the split-brain prevention. A node that declares itself leader must have a quorum of acknowledgments, so a minority partition cannot elect a leader. The quorum is a majority of the membership, so two disjoint majorities cannot exist, which prevents split-brain. A partition that leaves a majority can elect, and a minority cannot, which is the correctness guarantee.

The message complexity is O(n^2) in the worst case, because every node may send to every other node. For a small cluster this is fine; for a large cluster a ring algorithm or a consensus protocol is better, because they have lower message complexity.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A network transport between nodes
• Unique node ids and known membership

The dependencies cover the core needs:

• node:net (built-in) — TCP transport for election messages

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

leader-election-bully/ is organized so each concern is testable in isolation:

leader-election-bully/
├── src/election.ts
├── src/heartbeat.ts
├── src/leader.ts
├── tests/election.test.ts
└── package.json

Phase 1: Detect failure

A node that misses the leader heartbeat for a timeout starts an election.

if (now - lastLeaderHeartbeat > TIMEOUT) startElection();

The timeout is long enough to avoid false failure but short enough to re-elect quickly.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Start election

Send an election message to all higher-id nodes; if none respond, declare self leader.

const higher = members.filter(m => m.id > self.id); if (higher.length === 0) declareLeader();

A node with no higher-id live nodes is the highest, so it wins.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Respond and escalate

A higher-id node that receives an election message responds and starts its own election.

onElection(() => { respond(); startElection(); });

The escalation ensures the highest live node eventually wins.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Announce coordinator

The new leader sends a coordinator message to all nodes to establish itself.

for (const m of members) send(m, {type:"coordinator", leader: self.id});

The coordinator message ends the election and all nodes accept the leader.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Start five nodes, kill the leader, and assert the highest-id live node becomes leader; kill the new leader and assert re-election; partition a minority and assert no leader in the minority (quorum).

The basic test starts five nodes, waits for the election, and asserts the highest-id node is the leader. The failover test kills the leader and asserts the highest-id live node becomes the new leader, proving the failure detection and re-election.

The escalation test starts an election from the lowest-id node and asserts the highest-id node wins, not the lowest, proving the escalation works. The coordinator test asserts every node receives the coordinator message and accepts the leader, so the election ends.

The quorum test partitions a minority of nodes and asserts no leader in the minority, because the minority cannot reach a quorum. The majority partition elects a leader, proving the quorum prevents split-brain.

The heartbeat test stops the leader heartbeat and asserts an election starts after the timeout, not before, proving the timeout is respected. The false-failure test delays the leader heartbeat but does not stop it, and asserts no election starts, proving the timeout avoids false failure.

The concurrent-election test starts two elections at the same time and asserts only one leader emerges, proving the coordinator message resolves the concurrency.

pnpm vitest run

Observability

Track the highest-id wins rate, the leader-election resource usage, and the error count as the three primary signals for the leader-election-bully system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the failure detection via heartbeat alongside the highest-id wins so a correlation is visible at a glance, because a rising failure detection via heartbeat with a stable highest-id wins means the system is doing more work per unit, not that it is failing.

Log every detect failure transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the leader-election identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the highest-id wins error rate crossing a threshold, the leader-election utilization exceeding a percentage, and the failure detection via heartbeat latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The leader-election-bully system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Run one election instance per node, with the membership configured identically on every node. A mismatched membership means two nodes have a different view of the cluster, which can cause inconsistent elections. The membership is static, so it is set at deployment, not at runtime.

Require a quorum to prevent split-brain. A network partition that leaves a majority can elect a leader, and a minority cannot, so the cluster has at most one leader. A deployment without a quorum can have two leaders in a partition, which is split-brain, and the resulting conflicts are worse than no leader.

Set the heartbeat timeout from the network latency and the leader processing time. A timeout that is shorter than a slow leader round trip triggers false elections; a timeout that is longer than a dead leader detection delays recovery. The timeout is a trade-off, and the right value depends on the deployment.

Monitor the election count and the leader changes. A high election count means the leader is flapping, which is a heartbeat timeout problem; a leader change is a failover, which is expected on failure. Both are operator signals.

Do not use the bully algorithm for large clusters. The O(n^2) message complexity is fine for a few nodes but wasteful for hundreds. A ring algorithm has O(n) messages, and a consensus protocol like Raft has better properties, so the bully algorithm is for small clusters where simplicity matters more than scale.

Security considerations

Treat every input to the leader-election-bully system as untrusted, because the highest-id wins path is the one place an external caller controls what the system processes. Validate the input shape before any leader-election operation, and reject early with a clear error rather than letting a malformed input propagate into the detect failure phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:net credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured leader-election-bully fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the highest-id wins endpoint per caller, because an unbounded leader-election operation is a resource leak as much as a security problem. A caller that can trigger the start election path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the detect failure logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The leader-election-bully system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the leader-election structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• O(n^2) messages in the worst case; not suitable for large clusters.
• The bully algorithm assumes reliable detection; a false failure triggers an unnecessary election.
• Static membership; adding a node requires a restart.

The message complexity is O(n^2) in the worst case. Every node may send an election message to every higher-id node, and every higher-id node may respond and escalate. For a small cluster this is a few dozen messages; for a large cluster it is thousands, which is wasteful. A ring algorithm or a consensus protocol is better for large clusters.

The algorithm assumes reliable failure detection. A false failure, where the leader is alive but the heartbeat is delayed, triggers an unnecessary election, which is disruptive but not incorrect. The timeout is the trade-off, and a longer timeout reduces false failures but slows recovery.

The membership is static. Adding a node requires a restart, because the membership is not gossiped. A dynamic membership protocol, where nodes join and leave at runtime, is a real improvement but out of scope, because it requires a reconfiguration protocol that the bully algorithm does not have.