Coordination, Consensus, Leader Election, Leases, and Distributed Locks - Complete Notes

A language-neutral guide to making safe shared decisions under partial failure, understanding Raft, using leaders and leases correctly, fencing stale owners, choosing coordination primitives, and explaining production trade-offs in system-design interviews.

00. Mental model and precise terminology

Coordination is the work required when independent participants must agree before an action is safe.

01. Why coordination is expensive

Coordination places network delay and shared availability on a path that could otherwise be local.

Independent work scales well because each participant can proceed without waiting. Coordination adds messages, durable writes, quorum waits, serialization, contention, and recovery state. In a healthy three-node regional cluster, one committed update usually needs a leader disk write plus an acknowledgement from at least one follower. Across regions, the speed of a majority path and its tail latency matter. During a partition, the minority must stop accepting decisions if safety is to remain intact.

Design to minimize coordination

• Partition ownership so unrelated keys decide independently.
• Move invariants into one transactional authority where possible.
• Use immutable identifiers and append facts instead of overwriting shared state.
• Make commands idempotent so retries and duplicate leaders do not duplicate effects.
• Pre-allocate ranges or quotas when bounded temporary divergence is acceptable.
• Keep consensus metadata small. Store large payloads in systems designed for bulk data.
• Coordinate the smallest decision, then do parallel work outside the critical section.

02. Consensus goals, assumptions, and limits

Safety and liveness properties

Agreement

No two correct participants decide different values for the same slot.

Validity

A decided value follows the protocol's proposal rules rather than appearing from nowhere.

Integrity

A participant decides at most once for a given slot.

Termination

Correct participants eventually decide when the assumptions required for progress hold.

Safety says nothing bad happens, such as applying two different commands at log index 42. Liveness says something good eventually happens, such as a submitted command committing. A sound protocol preserves safety through partitions and pauses. It may deliberately sacrifice liveness when it cannot contact a quorum.

Fault model and the majority rule

Standard Raft assumes crash faults and non-Byzantine participants. A node may stop, restart, lose volatile state, or become unreachable, but it is not assumed to forge messages maliciously. Durable protocol state must survive restart. Authentication and transport integrity prevent outsiders from pretending to be voting members, but they do not turn Raft into a Byzantine consensus protocol.

majority(N) = floor(N / 2) + 1
crash_failures_tolerated = floor((N - 1) / 2)

3 voters - quorum 2 - tolerates 1 unavailable voter
5 voters - quorum 3 - tolerates 2 unavailable voters
7 voters - quorum 4 - tolerates 3 unavailable voters

Two majorities of the same membership intersect in at least one voter. That intersection carries information from an earlier decision into a later election or decision. Four voters still require three for a strict majority and tolerate only one unavailable voter, so adding a fourth voter does not improve crash tolerance over three. Odd voter counts usually use resources more efficiently. Non-voting replicas can serve other needs but do not change quorum safety.

Why timeouts cannot prove failure

In an asynchronous network, a silent node might be dead, paused by the runtime, isolated by a firewall, overloaded, or merely behind a delayed packet. A timeout can justify suspicion and a new election, but cannot establish truth. Consensus algorithms therefore use logical generations and quorum evidence rather than trusting a local timeout alone. Progress requires a period of enough synchrony for messages and processing to complete, even though safety does not depend on a fixed delivery bound.

03. Replicated state machines

Consensus commonly agrees on an ordered log, then deterministic state machines replay that log.

client command with request_id
          |
          v
       leader
     append locally
       /       \
 AppendEntries AppendEntries
     /           \
 follower       follower
     \           /
      majority durable acknowledgement
                 |
                 v
            commit index advances
                 |
                 v
       every replica applies in order
                 |
                 v
          deterministic state

Each log entry contains a command and protocol metadata such as index and term. Committed entries form the authoritative order. Applying the same deterministic command sequence yields the same state. External time, random numbers, remote API calls, and process-specific values must not be read nondeterministically during state-machine application. Put a chosen value into the command first or treat external effects as a separate idempotent workflow.

04. Raft roles, terms, and state

Raft separates leader election, log replication, and safety so each part can be reasoned about.

Durable and volatile protocol state

• currentTerm is durable so a restart cannot vote in an old generation.
• votedFor is durable so a server cannot grant two votes in one term after restart.
• The log is durable before acknowledging its entries.
• commitIndex tracks the highest known committed entry.
• lastApplied tracks the highest entry applied to the local state machine.
• A leader tracks nextIndex and matchIndex for each follower.

on receive(message):
  if message.term > currentTerm:
    persist currentTerm = message.term
    persist votedFor = none
    role = FOLLOWER

  if message.term < currentTerm:
    reject with currentTerm
  else:
    handle according to role and message type

05. Raft leader election

Election flow

1. Followers reset an election timer when valid leader contact arrives.
2. A timed-out follower increments its term, becomes candidate, persists its self-vote, and sends vote requests.
3. A voter grants at most one vote per term and only if the candidate's log is at least as up to date.
4. A candidate with a majority becomes leader and immediately establishes authority with heartbeats.
5. A candidate seeing a higher term steps down. A split vote waits for another randomized timeout.

Randomized election timeouts reduce repeated split votes. The heartbeat interval must be comfortably shorter than the election timeout. Election timeouts should exceed normal network, disk, runtime pause, and scheduling delay, but not be so large that genuine failure recovery violates the service objective. A fixed timer copied from a tutorial is not an operations policy.

candidate_is_up_to_date =
  candidate.lastLogTerm > voter.lastLogTerm
  OR (
    candidate.lastLogTerm == voter.lastLogTerm
    AND candidate.lastLogIndex >= voter.lastLogIndex
  )

grant vote only if:
  request.term == currentTerm
  AND (votedFor is none OR votedFor == candidate)
  AND candidate_is_up_to_date

The freshness check is a safety rule, not a preference for the busiest node. It prevents a candidate missing committed information from winning. CPU, zone, version, or workload preference can guide a planned handoff only if the core election safety rules remain intact.

Partition timeline

time       A(old leader) B        C        D        E
t0         leader        follower follower follower follower
t1         | isolated minority  | |       connected majority      |
t2         heartbeats to B        C times out, starts higher term
t3         A+B cannot commit      C receives C+D+E votes
t4         stale A may look alive C becomes leader and commits with D/E
t5         partition heals        A sees higher term and steps down

A can still believe it is leader locally because failure detection is imperfect. It cannot commit new Raft entries because two of five is not a majority. If A can mutate an external system that does not check authority, split-brain damage remains possible. This is exactly where fencing or a single transactional authority matters.

06. Log replication, matching, and commitment

AppendEntries consistency check

The leader sends the index and term immediately before the new entries. A follower accepts only if that preceding entry matches. On conflict, the follower removes the conflicting suffix and accepts the leader's suffix. The leader backs up the follower's next index until a matching prefix is found.

leader propose(command):
  entry = (index = log.end + 1, term = currentTerm, command)
  durably append entry
  send AppendEntries to followers

follower AppendEntries(prevIndex, prevTerm, entries, leaderCommit):
  if local log does not contain (prevIndex, prevTerm): reject
  delete local suffix that conflicts with entries
  durably append missing entries
  commitIndex = min(leaderCommit, local last index)
  acknowledge

leader after acknowledgements:
  if an index N from currentTerm exists on a majority:
    commitIndex = max(commitIndex, N)
    apply committed entries in order

The current-term commit rule

A Raft leader advances commitment by counting replicas only for an entry from its current term. When that current-term entry commits, preceding entries become committed indirectly through log matching. Counting an older-term entry merely because it appears on a majority can be unsafe in a particular leadership history. This nuance is a common senior interview question.

Client completion and deduplication

Reply after the command is committed and its result is known according to the implementation's contract. A response can still be lost. Clients send a stable request ID; the state machine stores the result indexed by client and request sequence. A repeated command returns the stored result. Bound deduplication retention according to retry windows, and make expiry semantics explicit.

Linearizable reads

A local leader read is unsafe immediately after a partition because the server may be an old leader. A conservative path records the read through the log. Optimized approaches confirm current-term leadership with quorum communication and wait until the state machine has applied through a safe read index. Lease reads can avoid a quorum round trip only when the implementation's timing assumptions are justified. Follower reads are usually stale unless a protocol supplies a bound or linearizable read mechanism.

07. Membership changes, snapshots, and recovery

Safe membership changes

Replacing a configuration in one local step can create two disjoint majorities, each believing it may decide. Raft's joint-consensus approach commits an intermediate configuration in which decisions require majorities from both old and new voter sets. After that entry commits, the new-only configuration can commit. This overlapping decision period preserves quorum intersection.

C_old = {A, B, C}
C_new = {C, D, E}

1. commit joint configuration C_old,new
   requires a majority of C_old AND a majority of C_new
2. operate under joint rules while new members catch up
3. commit C_new
4. removed members stop participating after learning the decision

Operationally, change one voter at a time unless the implementation documents a different safe procedure. Catch up a learner before promotion, avoid removing several members during degradation, and never edit membership files independently on nodes. Membership is protocol state.

Snapshots and log compaction

Logs grow without bound unless old committed entries are compacted. A snapshot records state through an included log index and term. After the snapshot is durable and validated, earlier log entries can be discarded. A far-behind follower receives an install-snapshot operation, verifies it, installs it atomically, then resumes replication after the included index.

• Do not snapshot uncommitted state or omit the included index and term.
• Use checksums, atomic replacement, and crash-safe metadata.
• Throttle snapshot transfer so recovery does not starve quorum traffic.
• Test restoring a snapshot plus the retained log, not just taking backups.
• Retain enough log for normal lag so every slow follower does not need a full snapshot.

Crash recovery

On restart, a member reloads durable term, vote, log, and snapshot state before participating. It must not serve authoritative reads until it has established safe leadership or a documented read guarantee. Disk corruption, lost acknowledgements, partial writes, and stale data directories are different from ordinary process crashes and need checksums, backup restoration, and operator procedures.

08. Raft and Paxos at a high level

Raft and Multi-Paxos can provide equivalent replicated-log safety, but organize the explanation and implementation differently.

Do not claim that Paxos has no leader, that Raft works without quorum intersection, or that one is universally more correct. Protocol families include many variants, optimizations, and membership schemes. In an interview, explain one model precisely, state the failure assumptions, and avoid implementing a new consensus protocol for production unless that is the product's core expertise.

09. Heartbeats and failure detectors

A heartbeat is evidence of recent communication, not proof of health. It can carry term, replication, and commit information. A missing heartbeat causes suspicion after a timeout. A process may still be running yet unable to reach storage, may reach some peers but not others, or may be paused long enough to lose authority and later resume.

Timeout design

Measure round-trip delay, durable-write latency, runtime pauses, scheduling delay, packet loss, and maintenance events. Pick a heartbeat interval that detects loss early enough without excessive write and network cost. Pick an election or session timeout with margin above healthy tail behavior. Alert when healthy observations approach the timeout because the cluster is close to unnecessary elections. Randomize contender timeouts to reduce simultaneous acquisition.

10. Leases and clock assumptions

A lease grants authority for a bounded interval, but safe use depends on whose clock defines that interval.

Lease states

NO_LEASE
  | acquire through authoritative store
  v
ACTIVE(token, deadline)
  | renew succeeds with enough safety margin
  +------------------------------> ACTIVE(new deadline)
  |
  | renewal ambiguous, local deadline near, pause, or store unavailable
  v
UNCERTAIN
  | stop starting work; cancel or fence in-flight writes
  v
EXPIRED
  | only a fresh acquire may restore authority
  v
NO_LEASE or ACTIVE(newer token)

A lease holder must stop before its locally safe deadline, not at the authority's nominal expiry instant. The safety margin accounts for clock drift, message delay, processing time, and pauses. A wall clock can jump due to correction or manual change. Use a monotonic clock for measuring local elapsed time. If the design compares clocks on different machines, document maximum skew and drift bounds, how they are maintained, and what happens when those bounds are violated.

Why renewal can fail

• The renewal never reaches the authority.
• It commits, but the acknowledgement is lost, creating an ambiguous result.
• A runtime or virtual machine pause exceeds the safe interval.
• The holder's network path works in one direction but not the other.
• The authority loses quorum and cannot commit renewal.
• Authentication, authorization, quota, or certificate rotation rejects the request.
• Clock error exceeds the design's promised bound.
• A slow renewal response arrives after a newer owner already acquired the lease.

Safe timing intuition

t0 = local monotonic time immediately before acquire request
authority grants lease duration L
reply arrives at local time t1

conservative local deadline = t0 + L - safety_margin

Why t0 instead of t1?
The lease may have started while the request or response was in flight.
Using t1 would assume authority lasted longer than evidence supports.

An implementation can provide a stronger documented contract, but callers should never invent one. Renew well before the deadline, stop admitting new work when renewal is uncertain, and expose lease remaining time as a metric. Do not persist a local lease across process restart unless the protocol explicitly supports that behavior.

11. Fencing tokens prevent stale-owner corruption

Mutual exclusion is not enough when a former owner can resume after its authority expired.

Failure timeline without fencing

1. allocator A acquires lock and reads available = 1
2. A pauses for longer than lock TTL
3. lock expires
4. allocator B acquires lock and reads available = 1
5. B writes available = 0 and confirms order B
6. A resumes with stale state
7. A writes available = 0 and confirms order A

Result: two orders were confirmed for one unit.
The lock service behaved according to its TTL contract.

Fenced write protocol

acquire("inventory:sku-42") returns token 731
next acquire returns token 732

inventory row stores last_fence

function allocate(sku, quantity, token, request_id):
  begin transaction
  row = select inventory for update
  if token <= row.last_fence:
    reject STALE_OWNER
  if row.available < quantity:
    reject OUT_OF_STOCK
  update row:
    available = available - quantity
    last_fence = token
  insert unique allocation(request_id, sku, quantity)
  commit

In the earlier timeline, B writes token 732. When A resumes with 731, inventory rejects it. Tokens must increase for each ownership generation and be compared by the resource that can corrupt state. A random lock-owner ID proves identity but not freshness. A timestamp is unsafe unless its ordering contract is strong enough. A consensus log revision, database sequence, or monotonically increasing version can supply a token when the full path preserves ordering.

12. Distributed mutexes and lock lifecycle

Required properties

• Mutual exclusion: conflicting valid owners are not granted simultaneously.
• Ownership: only the owner can release or renew its generation.
• Dead-owner recovery: a crash does not block progress forever.
• Fencing: later ownership can supersede stale in-flight work.
• Fairness: when required, waiting contenders are not starved.
• Bounded waiting: callers have deadlines and cancellation.
• Observable state: acquisition delay, contention, expiry, and ownership are inspectable.

owner_id = secure random unique value
(acquired, token) = coordinator.tryAcquire(lock_key, owner_id, ttl)

release must be one atomic operation:
  if stored owner_id == my owner_id:
    delete lock

Never do:
  GET lock
  if mine: DELETE lock

The lease may expire and another owner may acquire between GET and DELETE.

Owner checking prevents deleting somebody else's lock, but it is not fencing. Acquisition and protected work also need a defined transaction boundary. Keep critical sections short, propagate cancellation, set a maximum queue wait, and decide whether an ambiguous acquire is retried with the same attempt identity or discovered through coordinator state.

Granularity and deadlocks

A global lock is simple but serializes unrelated work. Fine-grained locks increase throughput but add key management and deadlock risk. If an operation needs several locks, acquire them in one canonical order, use bounded waits, and release all on failure. Detect wait-for cycles where the coordinator supports it. Prefer one atomic state transition when multiple-lock correctness becomes difficult to prove.

13. Semaphores, barriers, and coordination recipes

Lease-backed semaphore

Represent K permits as individually leased slots or an atomic count plus owner records. Acquisition must never observe a count and decrement it in separate unprotected operations. On expiry, reclaim the permit, but fence any external activity that could continue. Use a semaphore for capacity, not as a hidden queue with unbounded waiters. Admission requests need deadlines and fairness policy.

Generation-aware barrier

join(barrier_id, generation, participant_id, session_lease)

transactionally:
  reject if generation is closed
  add live participant for generation
  if live_count == required_count:
    mark generation OPEN

wait by watching the generation state, then re-read it
never treat a notification alone as the state
abort or advance according to policy if a participant lease expires

The generation prevents a delayed participant from joining the next run accidentally. A timeout policy must say whether the barrier aborts, reduces its required count, or waits for operator action. Notifications are hints: reconnect, re-read authoritative state, and handle missed events.

14. Coordination services and database primitives

Use a battle-tested service whose guarantees match the recipe, then keep the coordinated state small.

Sequential-node election and lock intuition

Apache ZooKeeper documents recipes based on ephemeral sequential nodes. Each contender creates a uniquely sequenced child. The lowest sequence becomes leader or lock owner. Instead of every waiter watching the owner and causing a herd on release, each contender watches only its immediate predecessor. If the predecessor disappears, it re-reads children and re-evaluates. A client must handle the ambiguous case where create succeeded but its response was lost, commonly by embedding a unique attempt identifier and discovering the created node.

Watches are notifications, not state

• Read current state and a revision before waiting.
• Process events in documented order and detect compaction or revision gaps.
• After disconnect, perform a full authoritative re-read.
• Make event handlers idempotent because reconnect logic may repeat work.
• Avoid making every waiter watch one key when predecessor watching is available.

15. When a constraint or idempotent operation is safer

begin transaction

insert into payment_requests(idempotency_key, status)
values (:key, 'PROCESSING')
on conflict (idempotency_key) do nothing

if insert did not happen:
  return the durable result for :key

perform the transactionally owned state change
store durable result for :key
commit

PostgreSQL unique constraints are enforced through unique indexes, and its advisory locks carry application-defined meaning that PostgreSQL itself does not enforce. This illustrates the general rule: a declarative constraint protects every write reaching the database, while an advisory lock protects only cooperating code paths. Choose the invariant at the narrowest authoritative boundary.

16. Case study: leader-elected scheduler

Electing one scheduler reduces duplicate dispatch, but durable run identity and idempotent workers provide business correctness.

Workload and assumptions

• Three scheduler replicas run across three failure zones.
• There are 200,000 recurring notification schedules and 2,000 due runs per second at peak.
• A run may be delayed briefly during failover, but it must not be lost.
• Duplicate dispatch is possible and workers must make duplicate effects harmless.
• The coordination service stores only leadership metadata, not the whole schedule catalog.
• The schedule database is authoritative for due time and durable run records.

scheduler replicas
 A  B  C
  \ | /
 coordination service - lease + monotonically increasing leader token
          |
          | active leader token T
          v
 schedule database - conditional claims + unique schedule_id/run_time
          |
          v
 durable work queue
          |
          v
 idempotent notification workers - provider request id

State and invariants

Protocol-first pseudocode

loop until shutdown:
  (lease, fence) = coordinator.acquire("notification-scheduler")
  if not acquired:
    wait with jitter and observe current owner
    continue

  while lease has safe remaining time:
    due = database.read_due_schedules(now, bounded_batch)
    for schedule in due:
      transactionally:
        reject if fence < schedule.last_leader_fence
        insert run(schedule.id, schedule.next_due) with unique run key
        advance next_due and store last_leader_fence = fence
        insert outbox(run.id)
    renew early

  stop admitting batches
  cancel database work where possible
  discard local authority even if renewal outcome was ambiguous

Small TypeScript example

The interfaces below expose the design rather than defining a particular coordination product. The abort signal carries deadline and leadership loss into database work.

type Leadership = {
  fence: bigint;
  safeUntilMs: number;
  renew(): Promise<boolean>;
  release(): Promise<void>;
};

async function lead(leadership: Leadership, stop: AbortSignal) {
  try {
    while (!stop.aborted && Date.now() < leadership.safeUntilMs) {
      await schedules.claimDueBatch({
        limit: 250,
        leaderFence: leadership.fence,
        signal: stop,
      });

      if (!(await leadership.renew())) break;
    }
  } finally {
    await leadership.release();
  }
}

Real code should measure lease time with a monotonic clock, renew independently of batch cadence, stop before the safe deadline, classify ambiguous renewal, and avoid assuming release succeeds. The database must reject a stale leaderFence; the loop alone is not a safety boundary.

Failover timeline

1. Replica A owns token 90 and commits runs through 10:05.
2. A pauses after writing a run but before receiving its transaction response.
3. A's lease expires. Replica B acquires token 91.
4. B retries the due run. The unique run key reveals A's committed result.
5. B safely advances later schedules with token 91.
6. A resumes. Its token 90 is rejected by the database, so it stops.
7. The outbox relay publishes any committed run whose response A missed.

Scaling the scheduler

One leader may become a throughput bottleneck. Partition schedules by stable hash or tenant region, then elect one leader per partition. Store an assignment epoch and move partitions gradually. Each partition retains its own run uniqueness and fence. A hundred partition leaders spread over several replicas is usually better than placing all scheduling work behind one global lock.

17. Case study: fenced inventory allocator

The allocator protects scarce stock by combining partitioned ownership, resource-side fencing, atomic quantity checks, and idempotent reservation records.

Workload and assumptions

• 50,000 allocation attempts per second with strong hot-key skew during product launches.
• Overselling is forbidden for scarce inventory; conservative rejection is acceptable.
• Reservations expire after 15 minutes and a separate workflow releases them idempotently.
• Each SKU has one authoritative inventory partition at a time.
• Clients retry ambiguous results with the same reservation ID.

Allocation flow

order service
  | reserve(sku, qty, reservation_id)
  v
allocator router - routes by sku partition
  |
  v
current allocator owner, epoch 405
  | transaction(sku, qty, reservation_id, fence=405)
  v
inventory authority
  - unique reservation_id
  - available quantity
  - highest accepted fence per partition
  - atomic conditional update
  |
  v
durable reservation result

Ownership transfer

1. allocator A owns partition P with fence 405
2. coordinator stops renewing or revokes A
3. A stops accepting new work and drains only while still safely authorized
4. allocator B acquires P with fence 406
5. router learns B's assignment revision
6. inventory accepts fence 406 and records it
7. delayed write from A with 405 is rejected
8. client retries the same reservation_id against B

Resource transaction

allocate(request):
  begin

  existing = reservation by request.reservation_id
  if existing exists:
    return existing durable result

  inventory = lock authoritative sku row

  if request.fence < inventory.highest_fence:
    rollback and return STALE_OWNER

  if inventory.available < request.quantity:
    record durable OUT_OF_STOCK result
    commit and return result

  update inventory:
    available = available - request.quantity
    highest_fence = request.fence

  insert reservation with unique reservation_id
  commit and return RESERVED

Hot-key choices

18. Production architecture and deployment

Place voters by failure domain

Put voters on independent machines and, where latency permits, independent zones. Three processes on one host are one failure domain. Avoid placing a majority behind one power, network, storage, or maintenance boundary. A five-voter cluster spanning three zones might use a 2-2-1 placement, but capacity planning must test which zone loss leaves a reachable majority and enough application capacity.

Regional and multi-region choices

A regional quorum usually has lower write latency. A multi-region quorum can survive a region loss but places inter-region latency and network reliability on the commit path. A two-region layout is awkward because either one region has quorum priority or losing connectivity stops progress. Three regions can distribute voters, but normal commits may wait across regions. State the latency and disaster objectives before choosing placement.

Safe upgrades

1. Verify backups, restore procedure, quorum health, and spare capacity.
2. Confirm protocol and storage-format compatibility across versions.
3. Upgrade one non-leader voter at a time and wait for catch-up.
4. Transfer leadership when needed rather than killing it repeatedly.
5. Keep a quorum of compatible healthy voters throughout.
6. Do not combine version change, membership change, and machine move in one step.
7. Validate election rate, replication lag, disk latency, and client errors after each step.

Backup and restore

A snapshot is not a recovery plan by itself. Record cluster identity, membership, encryption keys, application schema version, included log position, and restore procedure. Test restoring into an isolated environment and verifying application invariants. Never start multiple restored clusters with the same identity and endpoints where clients can reach both.

19. Observability and troubleshooting

Essential metrics

Logs and traces

Structured events should include cluster ID, member ID, term, role, peer, log index, commit index, lease ID, fencing token, lock key hash, request ID, and outcome. Do not log secrets or raw sensitive resource keys. Trace a proposal from client through leader replication and application, but sample high-volume heartbeats. Correlate leadership changes with disk, network, and runtime evidence.

Troubleshooting a flapping leader

1. Confirm impact: commit latency, failed proposals, lease churn, and stale-token rejection.
2. Build a term timeline from all voters using monotonic event order where available.
3. Check quorum reachability in both directions, not only client-to-server health.
4. Compare peer round-trip and durable-write tails with election timeout.
5. Inspect CPU throttling, long pauses, snapshots, compaction, and disk saturation.
6. Verify membership and endpoints are identical and no restored duplicate cluster exists.
7. Mitigate by removing overload or repairing the failed path while preserving quorum.
8. Change timeouts only after understanding the distribution; larger timers can hide failure.

20. Security, privacy, abuse, and trust boundaries

Trust boundaries

• Authenticate members mutually and authorize cluster membership changes separately from client writes.
• Encrypt client and peer traffic, verify host identity, and rotate certificates without losing quorum.
• Use least-privilege credentials per application and restrict each lock or key namespace by tenant.
• Protect snapshots, logs, and backups because coordination values can contain topology and secrets.
• Audit membership, lease ownership, administrative override, and destructive key operations.
• Validate that a token belongs to the expected resource namespace, not merely that it is numeric.

Abuse and denial of service

Attackers or buggy tenants can create millions of lock keys, hold permits, open watch streams, churn leases, or force hot-key contention. Enforce quotas on keys, sessions, watchers, request rate, transaction size, and history retention. Bound names and payloads. Separate administrative APIs. Avoid exposing raw coordinator errors or membership addresses to untrusted clients.

Compromised participants

Crash-fault consensus is not designed to remain correct when a voting member deliberately violates the protocol. Strong authentication reduces unauthorized membership but does not protect against a compromised authorized voter or malicious storage. If the threat model includes Byzantine faults, select a protocol designed for them, define identity and quorum assumptions accordingly, and expect higher message, operational, and latency cost.

Privacy

Lock and lease names can reveal tenant IDs, file paths, order IDs, or business activity. Prefer scoped opaque identifiers or keyed hashes, minimize retained history, and apply deletion and backup policies. Metrics should aggregate lock keys and control cardinality. Debug access to coordination state is privileged production data access.

21. Performance, scalability, capacity, latency, and cost

Commit latency model

commit latency is approximately the slower of:
  leader durable append
  fastest follower path needed to form a majority

plus:
  batching delay
  processing and queueing
  state-machine application if response waits for apply

throughput is bounded by the tightest of:
  leader CPU
  leader disk writes and bytes
  quorum network bandwidth
  follower durable writes
  state-machine apply rate

This is an intuition, not a universal formula. Implementations pipeline and batch replication, and acknowledgement contracts differ. Measure client-visible commit latency at p50, p95, p99, and p99.9. Tail disk and network behavior often matters more than averages because the quorum path must complete repeatedly.

Capacity example

Suppose leadership metadata receives 8,000 proposals per second, with 400 bytes of entry and protocol overhead per proposal. The raw leader log ingress is about 3.2 MB/s. Replicating to four followers sends roughly 12.8 MB/s before transport overhead, snapshots, retries, and reads. At 86400 seconds per day, the uncompacted raw entries are about 276 GB per day. This immediately motivates batching, compaction, retention limits, and keeping bulk payloads outside the coordinator.

Lock contention and queueing

If a critical section averages 20 ms, one exclusive lock has a theoretical ceiling near 50 owners per second before overhead. At high utilization, waiting time grows sharply and tail latency becomes unstable. Shorten the critical section, partition the key, batch compatible work, or replace the lock with an atomic operation. Adding coordinator nodes does not parallelize one hot lock.

Headroom planning

Size for a voter loss, snapshot transfer, compaction, backup, and application peak at the same time. A cluster that is 65 percent busy per voter may overload when traffic shifts after one failure. Preserve enough disk for log growth during an unavailable follower and enough network for catch-up without starving foreground quorum messages. Set hard payload and transaction limits.

22. Failure scenarios, edge cases, and safer corrections

Ambiguous outcomes

Timeout does not mean failure. An acquire, proposal, or release may have committed before its response disappeared. Every API needs an operation identity and a way to query or retry its outcome. Never convert a timeout directly into a second non-idempotent command. Record uncertainty explicitly and reconcile against authoritative state.

23. Testing strategy

Unit and model tests

• Test every role transition, term comparison, vote rule, and log-conflict case.
• Use deterministic clocks and schedulers to explore lease boundaries and delayed callbacks.
• Property-test that fencing tokens increase and stale tokens never mutate protected state.
• Test lock release with wrong owner, expired owner, and new owner interleavings.
• Model small protocol state spaces and assert agreement, leader completeness, and apply order.
• Test dedup retention and repeated requests before, during, and after expiry.

Integration and recovery tests

1. Start a real three or five voter cluster with isolated storage per member.
2. Commit data, kill a follower, restart it, and verify catch-up without lost commitment.
3. Kill the leader after durable append, after follower acknowledgement, and after commit but before client response.
4. Partition the old leader into a minority and verify it cannot commit or bypass external fencing.
5. Pause an owner beyond lease expiry, grant a new token, resume the old process, and expect rejection.
6. Corrupt or truncate a test snapshot and verify fail-safe recovery rather than silent state divergence.
7. Exercise safe membership addition, learner catch-up, promotion, removal, and rollback.
8. Disconnect a watch client through compaction and verify full re-read and correct resubscription.

History-based correctness testing

Record invocation and completion times, request IDs, returned values, terms, tokens, and authoritative state. Check whether completed operations admit the promised sequential or linearizable explanation. For locks, assert no two accepted protected writes violate fencing order. For the scheduler, assert a unique logical run and eventual outbox publication. For inventory, assert available quantity never becomes negative and every decrement has one durable reservation.

Load, stress, and soak tests

• Measure proposal and read percentiles at increasing load until saturation.
• Create one hot lock plus many cold keys to expose unfairness and head-of-line blocking.
• Run with one voter unavailable to prove failure headroom.
• Include compaction, snapshot, backup, certificate rotation, and follower catch-up.
• Soak long enough to observe log growth, watch leaks, session churn, and token exhaustion assumptions.
• Rate-limit fault injection so the test remains diagnosable and stop if safety evidence is lost.

Minimum fault matrix

24. Recovery playbook

Quorum unavailable

1. Freeze destructive automation and identify the exact configured voter set.
2. Determine which data directories contain the newest durable committed history without starting conflicting clusters.
3. Restore network, disk, credentials, or a stopped voter before attempting membership surgery.
4. Keep client writes blocked if quorum authority cannot be established.
5. Use the product's documented disaster-recovery procedure if quorum cannot be restored.
6. After recovery, verify cluster identity, membership, commit index, application invariants, and backups.

Lease or split-brain incident

1. Stop new protected operations or route them to a known safe authority.
2. Inspect fencing-token acceptance at the resource, not only coordinator ownership.
3. Identify every owner generation and effects written by each.
4. Advance authority using the documented revoke or election path.
5. Reconcile duplicated or stale effects using request IDs and audit history.
6. Preserve evidence: term, revision, tokens, clocks, pauses, and network events.
7. Fix the missing resource-side check or renewal policy before restoring ordinary traffic.

25. Hands-on exercises and design scenarios

Exercise 1: trace a Raft election

Given five voters, terms and last log positions are A=(7, 20), B=(7, 19), C=(6, 24), D=(7, 20), E=(5, 30), where each pair is (lastTerm, lastIndex). Candidate B requests votes in term 9. Which voters may consider B up to date?

Exercise 2: break and repair a TTL lock

Implement a test coordinator, pause owner A beyond TTL, allow B to acquire, then resume A. First use only owner IDs; observe both writes. Next return monotonically increasing tokens and make a database row reject tokens no greater than its highest token.

Exercise 3: design a scheduler

Design recurring billing for one million subscriptions, with a peak of 10,000 due runs per second, five-minute failover objective, and no duplicate charge. Explain partitioning, leadership, run identity, dispatch durability, payment idempotency, and recovery.

Exercise 4: plan voter replacement

Replace two old machines in a three-voter cluster while preserving write service. Write the exact order and failure checks.

Exercise 5: decide whether to coordinate

A content feed wants a globally exact view counter on every read. Peak load is two million reads per second and values may be a minute stale. Should every request use consensus?

26. Interview questions and detailed model answers

1. What problem does consensus solve?

Consensus lets participants agree on one irrevocable value or ordered command history despite some crash failures and delayed messages. In replicated state machines, it ensures replicas apply the same command at each log position. It preserves safety when a minority is unavailable, but progress normally requires a reachable majority and a sufficiently stable period of communication.

Follow-up: Why is consensus not the same as replication?

Replication means keeping copies. Without an agreement protocol, different copies can accept conflicting updates. Consensus defines which history is authoritative and when a value is chosen.

2. Why do majority quorums work?

Any two strict majorities of one membership intersect. A committed decision recorded on one majority cannot be completely hidden from a later majority. The protocol makes the intersecting voter carry accepted log or ballot information into elections and decisions. Intersection alone is not enough if clients bypass the protocol or membership changes create disjoint sets.

Follow-up: How many crashes do seven voters tolerate?

Three. Four votes remain required for a majority.

3. Explain a Raft election.

A follower missing leader contact reaches a randomized election timeout, increments its term, persists its self-vote, and requests votes. Each voter grants at most one vote in the term and only to a candidate whose log is at least as up to date. A majority elects the leader. Any participant seeing a higher term steps down or updates its term. Split votes cause another randomized round.

Follow-up: Can two nodes both think they are leader?

Locally, yes, during different terms or before an old leader learns of the new term. Two leaders for the same term cannot both obtain majorities from the same correct membership. External effects still need fencing because local belief can be stale.

4. What is Raft's log matching property?

If two logs contain the same index and term, they contain the same command there and identical preceding entries. AppendEntries includes the preceding index and term, so a follower rejects an extension that lacks the matching prefix. A new leader repairs conflicting uncommitted suffixes.

Follow-up: May an acknowledged entry be overwritten?

Yes, if acknowledgement meant only that one or some replicas stored it and the entry never became committed. A correctly committed entry is preserved by election and log safety rules.

5. Why does Raft count only current-term entries when advancing commit?

An older-term entry present on a majority can still be overwritten in a possible election history. A leader therefore advances commit by replica counting for an entry from its own term. Committing that entry indirectly commits all preceding entries through log matching and leader completeness.

6. How do Raft and Paxos differ?

Both can implement fault-tolerant replicated logs with comparable majority assumptions. Raft makes a strong leader and one coherent log central, with explicit terms and roles. Classic Paxos presents proposers, acceptors, learners, ballots, and one chosen value; Multi-Paxos repeats the process and uses a stable leader for efficiency. The most important interview skill is explaining one protocol accurately, not declaring a universal winner.

7. What is a lease, and why are clocks dangerous?

A lease is authority limited by time. Network delay means the holder may learn about a grant after some of its duration has passed. Clock skew, drift, jumps, and process pauses can invalidate naive comparisons. Measure local elapsed time with a monotonic clock, subtract safety margin, renew early, and stop on uncertainty. Use fencing for protected writes because a paused holder can resume.

Follow-up: Does clock synchronization eliminate fencing?

No. Synchronization has error bounds and does not eliminate runtime pauses or the gap between a local clock check and an external write.

8. Why is a distributed lock without fencing unsafe?

Lock ownership can expire while a process is paused. A new process acquires legitimately, then the old one resumes and still writes. A fencing token gives each ownership generation a greater number, and the protected resource rejects values older than the highest accepted number. Owner IDs prevent mistaken release, but only monotonic ordering checked at the resource prevents stale writes.

9. When is a database constraint better than a lock?

When the invariant lives in one database, a unique constraint, conditional update, row lock, or transaction makes the database the enforcement point for all writers. An application lock requires every path to cooperate and adds expiry and failure modes. Examples include unique usernames, payment idempotency keys, and decrement-if-available inventory.

10. How would you build a leader-elected scheduler?

Run replicas across failure domains and acquire a lease plus fencing epoch from a consistent authority. The active leader scans due work, but each logical run has a unique schedule and due-time key. Commit the run and an outbox record transactionally. Workers are idempotent. On uncertain lease renewal, stop starting work. The schedule database rejects old epochs. Partition the schedule space when one leader cannot handle peak load.

Follow-up: Why retain idempotency if there is one leader?

Failover can overlap local execution, responses can be lost, queue messages can repeat, and external effects can be ambiguous. Leadership is not an exactly-once guarantee.

11. How do you change consensus membership safely?

Use the implementation's reconfiguration protocol. In Raft joint consensus, an intermediate state requires majorities of both old and new configurations, preserving overlap. Operationally, catch up new members before promotion, change one member at a time, and confirm quorum after every step.

12. What causes leader flapping?

Election timeout too close to healthy tail latency, slow durable storage, CPU starvation, long runtime pauses, packet loss, overloaded event loops, snapshot work, or asymmetric network failure. Correlate term changes with peer latency, fsync tails, pauses, and quorum reachability. Increasing the timeout without diagnosis can only make actual failover slower.

13. What should happen when quorum is lost?

The cluster should preserve safety and stop committing decisions that require quorum. Applications may serve explicitly stale reads or degraded functions whose correctness allows it. Do not force a minority to accept writes. Restore a voter or network path, or use documented disaster recovery with a known authoritative history.

14. How would you test a distributed lock?

Generate concurrent histories, inject process pauses beyond TTL, network partitions, lost acquire and release responses, crashes, clock changes, and coordinator failover. Record tokens and accepted writes. Assert that the resource never accepts an older token after a newer one, wrong owners cannot release, ambiguous attempts can be discovered, and progress resumes after valid expiry.

15. Why should a coordination service hold little data?

Consensus turns every write into durable quorum work, and large values increase network, disk, log, snapshot, recovery, and compaction cost. Store membership, ownership, versions, and small metadata. Put bulk documents, media, analytics, or event payloads in systems designed for their access pattern.

27. Revision cheat sheet

• Coordinate only invariants that cannot be made local, partitioned, or idempotent.
• Consensus chooses one ordered history; replication alone only makes copies.
• Safety must survive partitions; liveness normally requires a reachable majority.
• A majority is floor(N / 2) + 1; five voters tolerate two unavailable voters.
• Raft uses followers, candidates, leaders, terms, votes, and a replicated log.
• Vote for at most one candidate per term and only when its log is sufficiently up to date.
• AppendEntries checks the preceding index and term to preserve log matching.
• Raft advances commit by counting a current-term entry, which indirectly commits prior entries.
• Uncommitted log suffixes can be overwritten after leadership change.
• Client request IDs handle committed commands whose responses were lost.
• Linearizable reads need current authority evidence and applied-state progress.
• Safe membership change preserves overlapping quorums.
• Snapshots include state plus last included index and term and must install atomically.
• Heartbeats and timeouts create suspicion, not proof of death.
• Use monotonic elapsed time, early renewal, and a safety margin for leases.
• An expired or paused owner can resume, so protected resources need fencing tokens.
• Owner IDs protect release; monotonic tokens protect resource writes.
• Mutex means one owner, semaphore means K permits, and barrier means wait for a phase.
• Notifications are hints. Re-read authoritative state after events and reconnects.
• Prefer database constraints and atomic updates when one database owns the invariant.
• A leader-elected scheduler still needs unique run IDs, outbox delivery, and idempotent workers.
• A fenced allocator also needs an atomic quantity check and unique reservation ID.
• Spread voters across failure domains and keep failure capacity headroom.
• Monitor term churn, quorum latency, fsync tail, lag, lease margin, and stale-token rejects.
• Never force-restore or manually break a lock without a documented fenced procedure.

28. Primary official references

• Ongaro and Ousterhout: In Search of an Understandable Consensus Algorithm, extended version - Raft roles, elections, log replication, safety, membership changes, and snapshots.
• USENIX ATC 2014 Raft publication page - peer-reviewed paper metadata, open paper, and presentation materials.
• Raft consensus algorithm official resource site - replicated-state-machine overview, paper, dissertation, formal specification, and implementations.
• Leslie Lamport: Paxos Made Simple - proposers, acceptors, ballots, chosen values, and the foundation for the high-level comparison.
• etcd API guarantees - ordering, linearizability, watches, leases, and documented API behavior.
• etcd concurrency API reference - lock, election, lease association, and concurrency service request contracts.
• Apache ZooKeeper Recipes and Solutions - barriers, ephemeral sequential-node locks, recoverable errors, and leader election.
• Apache Curator official recipes - production client recipes for locks, leader election, barriers, and related coordination patterns.
• Kubernetes official Lease documentation - leases used for node heartbeats and component leader election.
• Kubernetes coordinated leader election - Lease fields, optimistic concurrency, acquisition, renewal, and leadership transition.
• PostgreSQL explicit locking documentation - row, table, deadlock, and advisory-lock behavior and transaction scope.
• PostgreSQL index uniqueness checks - database enforcement of uniqueness under concurrent transactions.