The Consensus

Model Answer

FLP (Fischer, Lynch, Paterson 1985) proves that no deterministic algorithm can solve consensus in an asynchronous system if even one process can fail. "Asynchronous" means no upper bound on message delay. In practice, all real systems have timing assumptions (TCP timeouts, election timeouts), making them partially synchronous. Raft and Paxos work in the partially synchronous model — they may block during asynchronous periods but are always safe and make progress when synchrony resumes. FLP is a theoretical bound, not a practical barrier.

Model Answer

Paxos defines single-value consensus (single-decree Paxos). Multi-Paxos for a replicated log requires engineering decisions that are not specified in the original paper: how to pipeline proposals, how to handle leader changes, how to handle gaps in the log. Ongaro & Ousterhout found that real Paxos implementations (Chubby, Zookeeper ZAB) diverged significantly from the paper and from each other. Raft explicitly specifies leader election, log replication, and membership changes as a single coherent algorithm, making the design space tractable.

Model Answer

Use a Raft-replicated state machine where the lock state is a key-value entry. Acquire: propose "set lock = clientId" if lock is unset. Release: propose "set lock = nil" if lock == clientId. Add a TTL/lease to handle client crashes. Failure modes: (1) client crash while holding lock — use a lease that expires, (2) network partition — the leader might think it has the lock but is partitioned from the cluster. Use lease-based reads: the leader only serves reads while its lease is valid, which requires clock synchrony assumptions. HashiCorp Consul's session system implements exactly this.

Model Answer

A stale leader (on the minority side of a partition) still believes it is leader because it has not heard about the new higher-term election. Both the stale leader and new leader exist simultaneously. This is safe: the stale leader cannot commit any writes because it cannot reach a majority. Any write it tries will be rejected when the partition heals. The key safety property is that a stale leader's uncommitted writes are overwritten — only committed writes (replicated to majority) survive.

Model Answer

Linearizability: every operation appears to take effect instantaneously at a single point between its invocation and completion. A read always returns the result of the most recent write that completed before the read started. This matches single-machine memory semantics. Eventual consistency: if no new writes are made, all replicas will eventually converge to the same value. There is no guarantee about what a read returns during the convergence period. Tradeoff: linearizability requires coordination (quorum reads or leader reads), adding latency. Eventual consistency can serve reads locally, with lower latency but potentially stale data.