Distributed Systems Fundamentals Questions

Direct Answer

Paxos and Raft are both protocols that let a cluster of nodes agree on a value, or, in the log-replication case most real systems use, an ordered sequence of values, despite crashes and message delays, using a majority quorum so that any two decisions are guaranteed to have at least one node in common. Raft reaches the same safety guarantee as Paxos but organizes the protocol into named, sequential subproblems, mainly a single strong leader that serializes all writes during its term, which most engineers find much easier to implement correctly than Paxos's more general and symmetric design.

How Each Actually Reaches Agreement

Paxos (Multi-Paxos in practice). A proposer picks a proposal number and sends a Prepare message to the acceptors; each acceptor promises not to accept any proposal numbered lower and reports back the highest-numbered proposal it has already accepted, if any. Once the proposer hears back from a majority, it sends an Accept message carrying the value from the highest-numbered already-accepted proposal it was told about, not necessarily its own original value, and the value is chosen once a majority of acceptors accept it. Multi-Paxos elects a stable leader so that steady-state operation can skip repeating the Prepare phase for every new value.

Raft. Raft splits the same problem into leader election, where nodes agree on a single leader for a numbered term using randomized timeouts and majority votes, log replication, where the leader appends client commands to its own log and replicates them to followers, treating an entry as committed once a majority of nodes have stored it, and a safety rule that a candidate can only win an election if its log is at least as up to date as a majority of the cluster, which prevents a new leader from ever overwriting an already-committed entry.

Why Raft Is Easier to Implement and Reason About

Raft's decomposition gives each subproblem, who's the leader, how entries get replicated, how membership changes safely, its own explicit invariant, so an implementer can reason about one piece at a time. Paxos's proposer and acceptor roles are more general and symmetric, any node can propose at any time, which is elegant but produces more possible interleavings of concurrent proposals to reason about, especially once you move from the single-value textbook description to a real, steady-state, multi-value system, which is where most of the genuinely tricky Paxos engineering, such as stable leader election, log compaction, and membership changes, actually lives, and where the original paper says relatively little.

Comparison Table

A Worked Trace: Why a Competing Proposer Can't Just Overwrite the Value

Three acceptors, A1, A2, A3. Proposer P1 sends Prepare(1) to all three; none has accepted anything yet, so all three promise and report nothing. P1 gets a majority, 3 of 3, so it sends Accept(1, X). A1 and A2 accept proposal (1, X) before a second proposer, P2, starts a competing round. P2 sends Prepare(2) to A2 and A3; it doesn't reach A1. A2 has already accepted (1, X), so it promises not to accept below 2 and reports that it already accepted (1, X). A3 has accepted nothing, so it promises and reports nothing. P2 now has a majority of promises, A2 and A3, but because A2 reported an already-accepted value, the protocol requires P2 to propose that same value, X, rather than whatever value P2 originally intended. P2 sends Accept(2, X), not Accept(2, Y). Even though P2 won the second round, the value that gets chosen is still X. This is exactly the mechanism that keeps Paxos safe under concurrent proposers: a later round can change who proposes, but it cannot change what gets chosen once a value has reached a majority.

When to Still Reach for Paxos

Reach for Paxos, or a variant, instead of Raft when you're extending or must interoperate with an existing Paxos-based system where a rewrite isn't worth the risk, or when you need the extra flexibility Paxos's more general, symmetric design supports, such as non-majority or weighted quorum arrangements tuned for a specific wide-area latency profile, or when your team already has deep, tested Paxos expertise and infrastructure that a switch to Raft wouldn't meaningfully improve on.

When to Rely on an External Coordination Service Instead of Embedding Consensus Yourself

Most application teams don't actually need to choose between Raft and Paxos at all; they need a small set of coordination primitives, such as leader election for their own service, a shared lock, a bit of shared configuration, or service discovery, and implementing a correct Raft or Paxos group from scratch means owning a lot of subtle correctness surface, including log compaction, snapshotting, membership changes, and safe leadership transfer, for something an existing, battle-tested coordination service already does well. In that case, point your application at etcd, ZooKeeper, or Consul rather than embedding a consensus implementation. The case for building your own is when the consensus group needs to sit directly in your own data path for latency or throughput reasons, for example when you're building a replicated database yourself and every write needs to go through your own consensus group rather than round-tripping to an external service.

Trade-offs and Pitfalls

• It's a common misreading to treat Paxos as worse than Raft; it's a general, provably minimal algorithm. What actually makes it hard is that the original description covers a single value, and turning that into a real, steady-state, multi-value system requires additional engineering, such as a stable leader, log compaction, and membership changes, that Raft specifies as part of its core design instead of leaving as an exercise.
• Don't conflate which consensus algorithm to use with the more common real decision, which is whether to implement any consensus algorithm yourself at all; for most teams, depending on an existing coordination service is the right default, and only teams actually building infrastructure-level replicated systems typically end up choosing between Raft and Paxos directly.

Direct answer

Give the client a small piece of state recording what it has already seen, not what time it wrote at, and require every subsequent read to prove it reflects at least that much. Read-your-writes (RYW), the guarantee that once a client observes or performs a write, every later read in that same session reflects it or something newer, can be built with sticky routing, a session token carrying a single write position, or a version vector, and only the version vector survives a client moving to a different region mid-session.

Mechanism 1: sticky routing

Pin the entire session to the region the write went to. Simple to build, but availability degrades if that region becomes unreachable, and it fails outright the moment the client is routed to a different region.

Mechanism 2: session token with a scalar position

After a write, the client receives a token carrying (origin_region, write_position), a per-region monotonically increasing sequence number or log offset. On a later read, the serving replica compares its own applied position for that origin region against the token; if it has caught up, it answers locally, otherwise it waits, proxies to the origin, or serves from a short-lived read-after-write cache holding the write's payload directly. This works as long as the client only ever wrote in one region during the session.

Mechanism 3: version vectors

Instead of one scalar number, the token carries a vector of positions, one per region that could plausibly have accepted a write during the session: for example VV = {A: 5, B: 3}, meaning "I have seen everything through position 5 from region A and position 3 from region B." Any replica in any region can check RYW correctness against the whole vector, which is exactly what's needed once the client is no longer talking to the region it originally wrote in.

Worked example: a write in region A, then a migration to region B

sequenceDiagram
    participant Client
    participant A as Region A
    participant B as Region B
    Client->>A: write profile
    A-->>Client: ack, VV={A:5,B:0}
    Client->>A: read profile
    A-->>Client: local answer (A already at 5)
    Note over Client: migrates to Region B
    Client->>B: read profile, token VV={A:5,B:0}
    Note over B: B's replicated-from-A cursor = 3, behind 5
    B-->>Client: wait or proxy to A
    Note over B: cursor catches up to 5
    B-->>Client: local answer, VV={A:5,B:new}

1. Client, in a session against Region A, writes a profile update. Region A's local write-sequence advances to position 5. The client's version vector becomes VV = {A: 5, B: 0}: it has seen its own write at A's position 5, and has a floor of 0 for anything from B, since it hasn't observed anything from there yet.
2. Client reads its profile again, still talking to Region A: A's own applied position for itself is already at least 5 (it just accepted the write locally), so it answers directly. VV is unchanged.
3. The client's connection migrates to Region B mid-session. It presents its token VV = {A: 5, B: 0} to Region B.
4. Region B checks whether its own cursor for replication-from-A has reached position 5. Suppose B's cursor currently sits at A: 3, meaning it has only applied A's writes through position 3; the write at position 5 hasn't propagated across the inter-region link yet.
5. Since B's cursor (3) is behind what the token requires (5), Region B cannot honor read-your-writes from its current local state. It has three honest options: wait or briefly poll until its A-cursor reaches 5, proxy this one read to Region A directly, or check a short-lived read-after-write cache keyed by the write's own id if one exists. It must not simply answer from its current, stale-relative-to-the-token state.
6. Once B's cursor from A reaches position 5, whether by waiting or because the async pipeline naturally caught up, B answers locally and updates the client's token going forward to VV = {A: 5, B: <B's own current position>}.

Token expiry

Bound the token's validity window, for example expiring it after a period of client inactivity. On expiry, the client should not try to remember its "seen" state indefinitely; it should treat expiry as the session ending and fall back to whatever the default consistency level is for a fresh session. Indefinitely-lived tokens would force every replica to retain unbounded replication-position history purely to be able to compare against old tokens.

A failed request with an unknown outcome

If a write request times out with no clear success or failure response, the client does not yet know whether to advance its version vector. The safe rule is to only advance the "seen" vector once the client has positive confirmation, an acknowledgment carrying the write's assigned position; on an unknown-outcome timeout, the client must not assume the write happened. If the client then retries the write, that retry needs its own idempotency handling so a write that actually did succeed the first time doesn't get double-applied, which is a separate mechanism from RYW tracking itself: the version vector is only ever updated from a confirmed position, never a guessed one.

Trade-offs & pitfalls

Version vectors scale with the number of regions that could plausibly appear in a single session; fine at a handful of regions, unwieldy with dozens of independent write origins, in which case grouping by a coarser unit (a datacenter cluster rather than a single node) keeps the vector small. A common bug is comparing only the single most recent write's position once a client has actually written in more than one region during a session, which silently drops read-your-writes for the earlier region's write. Storing session state server-side instead of in a client-held token shifts the scaling concern from token size to session-storage capacity, which is a real trade to name rather than a free win.

Read-your-writes, monotonic reads, and monotonic writes are per-client session guarantees layered on top of a weaker (often eventually consistent) store, without paying for full linearizability across the whole system. Read-your-writes (RYW) promises a client that any read after its own write reflects that write. Monotonic reads promises a client's successive reads never go backwards in time. Monotonic writes promises a client's own writes are applied in the order it issued them. Each is enforced with a small piece of per-session state, not by coordinating the whole cluster.

What each guarantee promises, and how it breaks

Worked example: a monotonic-reads violation and its fix

Consider a likes counter on a post, replicated across replica X and replica Y with asynchronous replication.

Without the guarantee:

1. Client issues Read1, routed to replica X, which has applied all writes up to likes = 42. Client sees 42.
2. Client issues Read2 moments later. This time the request lands on replica Y, which has only applied writes up to likes = 40 (Y is lagging behind X). Client sees 40, a value older than what it already observed.

With the mechanism:
3. The client library remembers the highest value it has seen, last_seen_version = 42.
4. Read2 is sent with that version attached. Replica Y checks its own applied version (40) against the required version (42), sees it has not caught up, and either forwards the read to a replica that has (X, or any replica at version 42 or later) or holds the request briefly until its own replication catches up. The client never observes a regression.

Trade-offs and pitfalls

Sticky routing is the cheapest fix but weakens load balancing and complicates failover: if the pinned replica dies, the client loses its anchor, and if the guarantee is tied to a session cookie rather than the account, two devices logged into the same account (a phone and a laptop) are different sessions from the server's point of view and do not automatically share the guarantee with each other. Version tokens are more portable across devices and do not concentrate load onto one replica, but they add a token to every request and response, and the server still has to decide what a replica does when it cannot yet satisfy the token: wait, redirect, or refuse, which is itself a small latency-versus-freshness decision. Finally, these guarantees compose per client but do not add up to global consistency: a system can offer all three to every client individually and still allow two different clients to observe each other's writes in different orders. They make one user's own experience feel correct; they are not a substitute for linearizability when multiple clients must agree on a single order of events.

Direct answer

These three terms describe how many times a record's effect can show up downstream, not how many times it crosses the wire. At-least-once guarantees nothing is silently dropped but tolerates re-delivery, so duplicates are possible. At-most-once guarantees no duplicates but tolerates silent loss. Exactly-once means the record's effect appears exactly once, even though delivery itself is usually still at-least-once under the hood; the "exactly" part is enforced by deduplication or a transactional write, not by literally never redelivering anything.

At-least-once

Mechanism: the consumer commits its read offset only after it has finished processing a record.

Scenario producing a duplicate: a consumer reads offset 100 from a partition and processes it, say incrementing an inventory counter, but crashes before committing that offset. On restart it resumes from the last committed offset, 99, and re-reads and reprocesses offset 100, incrementing the counter a second time. The counter's effect happened twice for one logical record.

At-most-once

Mechanism: the consumer commits its read offset before processing the record.

Scenario producing a loss: a consumer commits offset 100 immediately on receipt, then crashes while processing that record. On restart it resumes from offset 100 onward, since that offset is already committed, so the record at offset 100 is never processed. This is the mirror image of the at-least-once bug: it's the same commit-versus-process ordering, flipped.

Exactly-once: what it actually takes at the consumer

• Idempotent processing: design the effect so applying it twice produces the same result as applying it once, for example replacing "increment counter by 1" with "set counter to max(current, computed value)", or recording each processed key in a table with a uniqueness constraint so a repeat attempt is rejected rather than reapplied.
• Dedup window: a bounded structure, such as a set of recently-processed record ids, that the consumer checks before applying an effect. It must be sized to cover the maximum plausible redelivery delay; if consumer restarts are the main cause of redelivery and offsets commit every 30 seconds, a window covering the last few minutes of ids is enough, but an outage longer than the window falls back on whatever uniqueness constraint the underlying store provides.
• Transactional writes: commit the output write and the offset advance as a single atomic operation, so a crash between "wrote output" and "committed offset" cannot happen. Kafka's transactional producer does this across topic-partitions; a database sink can do the same by writing the output row and a processed-offsets row inside one database transaction.

Worked example: exactly-once via a transactional write

Consumer is at offset 100. It opens a transaction, upserts the inventory row (an idempotent write), writes offset=101 to an offsets table, and commits the transaction atomically.

• If the consumer crashes before the commit: nothing happened; the output was never applied and the offset was never advanced. Re-reading offset 100 next time reproduces the exact same atomic attempt, with no partial effect ever visible in between.
• If it crashes after the commit: offset 101 is already recorded, so the consumer will not re-read offset 100 on restart.

There is no window in which the output exists but the offset doesn't, or vice versa, because both changes are part of one transaction.

Practical guidance

Trade-offs & pitfalls

Exactly-once adds real coordination cost (transactions, dedup lookups), so its throughput and latency are worse than plain at-least-once, which is why it's reserved for cases where correctness genuinely requires it rather than applied everywhere by default. A dedup window sized too small silently degrades to at-least-once during a long outage, without any error being raised. A common interview trap is conflating a broker-level exactly-once guarantee (Kafka's own transactions between its topics) with true end-to-end exactly-once: Kafka's guarantee stops at the Kafka cluster boundary, so if the final effect lands somewhere outside it, an external database or a third-party API, that external system still has to be transactional or idempotent for the guarantee to actually hold all the way through.

Linearizability and serializability sound similar but answer different questions. Linearizability is about a single object: every operation on it must appear to happen instantaneously at some point between when it was invoked and when it returned, and that ordering must match real time. Serializability is about multiple objects touched by a transaction: the outcome of running several transactions concurrently must be equivalent to running them in some serial order, but that order does not have to match real time or even the order the transactions actually started in. A system can have one property without the other, and assuming the wrong one silently breaks a different class of guarantee.

Two mechanisms that actually enforce serializability

• Two-phase locking (2PL): a transaction acquires every lock it needs before releasing any of them, and once it starts releasing locks it may acquire no more. This physically prevents conflicting concurrent access, at the cost of blocking and potential deadlock.
• Optimistic concurrency control (OCC): transactions proceed without locking, then get validated at commit time; if another transaction's concurrent writes conflict with what this one read, it aborts and retries. This avoids blocking under low contention but wastes work under high contention.

When you need one but not the other

Consider a key-value store advertising single-copy semantics: every replica must behave as if there is exactly one physical copy of the data, so any client reading a key right after a write, from any client, on any replica, sees that write or a later one, never a stale value. The same requirement shows up as a highly available configuration service needing linearizable reads: if a client reads a feature flag or a routing rule right after it changed, it must get the new value, since acting on a stale one applies the wrong policy. Neither of these needs serializability: there is no multi-key transaction to isolate, just one key's recency.

The mirror case: a reporting system running multi-row aggregate queries across many tables needs those queries to see an internally consistent snapshot (serializability, or at least snapshot isolation), but does not need that snapshot to be the absolute latest possible instant in real time. A report built from data a few hundred milliseconds behind the live system is fine, as long as every row it reads is mutually consistent with every other row it reads.

Worked example: what breaks if you assume the wrong one

Linearizable but not serializable, no cross-key transaction: a key-value store gives linearizable single-key reads and writes but has no multi-key transactions. A funds transfer moves 30 units from account A (currently 100) to account B (currently 50) as two separate linearizable writes: write A=70, then write B=80. A concurrent reader can land exactly between the two writes and read A=70 and B=50. Both individual reads are linearizable, each reflects the latest write to that specific key at the moment it was read, but the reader just observed a total of 70+50=120, when the true, fully-settled total is 70+80=150: 30 units appear to have vanished mid-transfer. That is the anomaly linearizability alone does not prevent, because it says nothing about atomicity across two different keys.

Serializable but write-skew possible, snapshot isolation only: a hospital scheduling system enforces one invariant, that at least one doctor remains on call.

$\text{doctors on call} \ge 1$

Two doctors, Alice and Bob, are both currently on call, so the on-call count is 2. Both, concurrently, read a snapshot showing 2 doctors on call and each independently decide it is safe to go off-call, and both commit that decision under snapshot isolation, since neither transaction's write conflicts with what the other actually wrote (each only writes their own on-call flag). The result: 0 doctors on call, violating the invariant, even though each transaction, viewed alone against its own snapshot, looks perfectly valid. Full serializability, not just snapshot isolation, would detect that these two transactions' reads and writes interfere and force one to abort; snapshot isolation's weaker check does not.

Trade-offs & pitfalls

• Common wrong turn: treating serializable as automatically meaning fresh or linearizable. It is not: transactions can be serialized in an order that does not match when they actually ran.
• Common wrong turn: treating a single-key linearizable store as if it gives transactional safety across several keys. It does not, by itself, unless the store also offers multi-key transactions on top.
• Snapshot isolation is cheaper than full serializability, since it does not need to detect every possible interleaving, only genuine write-write conflicts, and is what most production databases default to, which is exactly why the write-skew anomaly above shows up in practice more often than people expect.