What is leader election in distributed systems?

// Raft-style leader election on a fake clock: terms, majority votes,
// randomized timeouts, a crash, a partition and a fencing token.
const N = 5, LAT = 10, HB = 50; // nodes, one-way message delay (ms), heartbeat interval (ms)
let seed = 1;
function rnd() { // xorshift32, identical in every language
  seed = (seed ^ (seed << 13)) >>> 0;
  seed = (seed ^ (seed >>> 17)) >>> 0;
  seed = (seed ^ (seed << 5)) >>> 0;
  return seed;
}
function cluster(lo, hi, s, verbose) {
  seed = s;
  const c = { now: 0, lo, hi, verbose, msgs: [], group: [0, 0, 0, 0, 0], elections: 0, firstLeader: -1, winTerm: 0, nodes: [] };
  for (let i = 0; i < N; i++) c.nodes.push({ id: i, role: "follower", term: 0, voted: -1, votes: 0, alive: true, deadline: 0, nextHb: 0 });
  for (const n of c.nodes) n.deadline = timeout(c);
  return c;
}
function timeout(c) { return c.now + c.lo + (rnd() % (c.hi - c.lo)); }
function say(c, s) { if (c.verbose) console.log("t=" + c.now + "ms " + s); }
function send(c, from, to, type, term, ok) {
  if (c.group[from] === c.group[to]) c.msgs.push({ at: c.now + LAT, from, to, type, term, ok });
}
function broadcast(c, n, type) { for (let j = 0; j < N; j++) if (j !== n.id) send(c, n.id, j, type, n.term, false); }
function handle(c, n, m) {
  if (m.term > n.term) {
    if (n.role === "leader") say(c, "node " + n.id + " steps down: saw term " + m.term);
    n.term = m.term; n.role = "follower"; n.voted = -1;
  }
  if (m.type === "voteReq") {
    const ok = m.term === n.term && (n.voted === -1 || n.voted === m.from);
    if (ok) { n.voted = m.from; n.deadline = timeout(c); }
    send(c, n.id, m.from, "vote", n.term, ok);
  } else if (m.type === "vote") {
    if (n.role === "candidate" && m.term === n.term && m.ok) {
      n.votes++;
      if (2 * n.votes > N) {
        n.role = "leader"; n.nextHb = c.now;
        if (c.firstLeader < 0) { c.firstLeader = c.now; c.winTerm = n.term; }
        say(c, "node " + n.id + " wins term " + n.term + " with " + n.votes + " of " + N + " votes");
      }
    }
  } else if (m.type === "hb") {
    if (m.term === n.term) { n.role = "follower"; n.deadline = timeout(c); }
    else send(c, n.id, m.from, "hbReject", n.term, false);
  }
}
function run(c, until) {
  while (c.now < until) {
    while (c.msgs.length && c.msgs[0].at <= c.now) {
      const m = c.msgs.shift(), n = c.nodes[m.to];
      if (n.alive && c.group[m.from] === c.group[m.to]) handle(c, n, m);
    }
    for (const n of c.nodes) {
      if (!n.alive) continue;
      if (n.role === "leader") {
        if (c.now >= n.nextHb) { n.nextHb = c.now + HB; broadcast(c, n, "hb"); }
      } else if (c.now >= n.deadline) {
        n.role = "candidate"; n.term++; n.voted = n.id; n.votes = 1; n.deadline = timeout(c); c.elections++;
        say(c, "node " + n.id + " times out, candidate for term " + n.term);
        broadcast(c, n, "voteReq");
      }
    }
    c.now++;
  }
}
function leaderOf(c, g) {
  let best = -1;
  for (const n of c.nodes) if (n.alive && n.role === "leader" && c.group[n.id] === g && (best < 0 || n.term > c.nodes[best].term)) best = n.id;
  return best;
}

console.log("== 1. Cold start, timeouts random in [150, 300) ms, seed 42 ==");
const c = cluster(150, 300, 42, true);
run(c, 1000);
const l1 = leaderOf(c, 0);
console.log("t=1000ms leader node " + l1 + " crashes");
c.nodes[l1].alive = false;
run(c, 1600);
const l2 = leaderOf(c, 0);
console.log("failover: node " + l2 + " leads term " + c.nodes[l2].term + "; old node " + l1 + " restarts as follower");
c.nodes[l1].alive = true; c.nodes[l1].role = "follower"; c.nodes[l1].deadline = timeout(c);
run(c, 2000);
const buddy = l2 === 0 ? 1 : 0;
console.log("t=2000ms partition: {" + l2 + "," + buddy + "} cannot reach the other three");
c.group[l2] = 1; c.group[buddy] = 1;
run(c, 2600);
const l3 = leaderOf(c, 0);
console.log("t=2600ms node " + l2 + " still thinks it leads term " + c.nodes[l2].term + "; node " + l3 + " leads term " + c.nodes[l3].term);
for (const id of [l3, l2]) {
  let reach = 0;
  for (const n of c.nodes) if (n.alive && c.group[n.id] === c.group[id]) reach++;
  console.log("  write via node " + id + ": " + reach + " of 5 acks, " + (2 * reach > N ? "committed" : "NOT committed"));
}
for (const fenced of [false, true]) {
  let highest = 0, value = "none";
  const out = [];
  for (const [id, v] of [[l3, "A"], [l2, "B"]]) {
    const token = c.nodes[id].term;
    if (!fenced || token >= highest) { highest = Math.max(highest, token); value = v; out.push("token " + token + " accepted"); }
    else out.push("token " + token + " rejected");
  }
  console.log("  storage " + (fenced ? "with" : "without") + " fencing: " + out.join(", ") + "; final value " + value);
}
console.log("t=2600ms partition heals");
c.group[l2] = 0; c.group[buddy] = 0;
run(c, 2800);
console.log("leaders now: " + c.nodes.filter((n) => n.role === "leader").map((n) => "node " + n.id + " term " + n.term).join(", "));

console.log("\n== 2. Every node uses the same fixed 150 ms timeout ==");
const f = cluster(150, 151, 7, false);
run(f, 2000);
console.log("elections started: " + f.elections + ", leaders elected: " + (f.firstLeader < 0 ? 0 : 1));

console.log("\n== 3. 200 cold starts per timeout range (seeds 1..200) ==");
for (const [lo, hi] of [[150, 155], [150, 200], [150, 300], [150, 450]]) {
  let sum = 0, max = 0, retry = 0, failed = 0;
  for (let s = 1; s <= 200; s++) {
    const t = cluster(lo, hi, s, false);
    while (t.firstLeader < 0 && t.now < 5000) run(t, t.now + 1);
    if (t.firstLeader < 0) { failed++; continue; }
    sum += t.firstLeader; max = Math.max(max, t.firstLeader);
    if (t.winTerm > 1) retry++;
  }
  const ok = 200 - failed, avg10 = Math.floor((sum * 10 + Math.floor(ok / 2)) / ok);
  console.log("[" + lo + ", " + hi + ") ms: avg " + Math.floor(avg10 / 10) + "." + (avg10 % 10) + " ms to a leader, max " + max + " ms, needed more than one term: " + retry + ", no leader in 5 s: " + failed);
}