Distributed Systems Fundamentals Questions

Raft replicates a log by having the leader append every client command locally, then replicate it to followers via AppendEntries RPCs; once a majority, including the leader, has stored an entry, the leader marks it committed and applies it to its state machine, and followers catch up the same way once they learn the new commit index. A slow or long-disconnected follower gets caught up either by incrementally backfilling AppendEntries, or, if it has fallen too far behind, by receiving a full InstallSnapshot of compacted state. The reason two leaders can never commit conflicting entries at the same log position is not a single rule, it is two rules working together: how logs are kept consistent, the log-matching property, and who is even allowed to become leader, the election restriction.

Terms and leader election, brief recap

Each term has at most one leader, elected by majority vote (covered in depth elsewhere in this material); what matters for replication is just that every entry in the log is tagged with the term of the leader that created it.

AppendEntries and the commit rule

• The leader sends AppendEntries(prevLogIndex, prevLogTerm, entries, leaderCommit) to each follower. A follower only accepts the new entries if its own log already has an entry at prevLogIndex with term prevLogTerm, matching exactly. If it does not match, the follower rejects, and the leader backs off to an earlier index and retries; this is what repairs a follower whose log has diverged.
• An entry counts as committed once it, and transitively every entry before it, is stored on a majority of servers, and that entry was created in the leader's own current term. That second condition, from the leader's own term, is the subtle part; see the worked example below for why it is necessary.
• Once committed, the leader applies the entry to its state machine and advances leaderCommit, which followers learn on the next AppendEntries, including empty heartbeats, and apply locally too.

Log compaction via snapshotting

• When a follower has fallen far enough behind that the leader has already discarded, or compacted, the log entries it needs, the leader sends InstallSnapshot instead: a full compacted copy of state plus the index and term of the last entry included in it.
• The follower replaces its own log prefix with the snapshot and adjusts its own next-expected index accordingly, then resumes normal AppendEntries catch-up from there.

Why two leaders can never commit conflicting entries at the same position, in plain terms

Two facts, combined, make this impossible:

1. Log matching: if two servers' logs both contain an entry at the same index with the same term, every entry up to and including that index is identical on both. This holds because a leader never reorders or overwrites its own log during its term, it only appends, and every follower's AppendEntries acceptance check requires the previous entry to match exactly before accepting anything new.
2. Election restriction: a candidate can only win a vote from a node whose log is at least as up to date as the candidate's own, compared by last entry's term, then index. Since winning requires a majority of votes, and any already-committed entry was, by definition, stored on a majority, at least one voter in any winning majority must already hold that committed entry. Any two majorities out of the same n servers are guaranteed to overlap in at least one server:

$|Q_1| + |Q_2| > n \implies Q_1 \cap Q_2 \neq \emptyset$

That overlap is exactly why whoever wins an election has a log at least as up to date as a node that already holds any previously committed entry, so the new leader must already have it too. A new leader can extend the log with new entries, but it can never come into office missing, and therefore able to overwrite, something the cluster already agreed on.

The genuinely tricky part, and the reason committed equals majority replicated is not the whole rule, is entries a leader replicated to a majority before it finished committing them in its own term and then crashed. A later leader, elected without ever having seen that specific entry, could otherwise legally overwrite it, which is why Raft only counts an entry as truly committed once a majority holds an entry from the current leader's own term: committing that later entry transitively commits everything before it, by log matching, without ever needing to separately reason about whether an older, not-yet-current-term entry was safe on its own.

Worked example: why from the leader's own term matters, printed trace

Five servers, S1 through S5.

• Term 2: S1 is leader. It appends an entry at log index 2, call its value 'x', and replicates it to S1 and S2 only, 2 of 5 servers, not a majority, before S1 crashes.
• Term 3: S5 becomes leader; S5's log does not have 'x' yet, and that is fine, since 'x' was never committed and was never required for S5's election vote to be up to date. S5 overwrites index 2 with its own entry, 'y', replicates it to S5 and S3, 2 of 5, still not a majority, then S5 also crashes before committing it.
• Term 4: S1 restarts and is re-elected leader; its log, containing the old 'x' at index 2, is still eligible since 'y' was never committed to a majority either. S1 now replicates its old index-2 entry 'x' to a majority: S1, S2, and S3, 3 of 5. Index 2 now genuinely has 'x' on a majority of servers.

Here is the crux: if Raft's rule were simply committed equals majority replicated, index 2 (holding 'x') would now count as committed, purely because a majority happens to hold it, even though it was replicated under a different leader's term, term 2, than the one currently in power, term 4. Raft explicitly does not commit it on that basis alone. Only once S1, as term-4 leader, replicates a new entry from term 4 to a majority does index 2 become safely committed, as a side effect of committing that later entry, since log matching guarantees everything before it, including 'x' at index 2, is identical across that same majority too. Without this extra rule, a hypothetical term-5 leader that had never seen 'x' could still legally overwrite index 2 yet again, since nothing had actually locked it in, and that overwrite would silently undo something an operator might already have treated as durably committed.

sequenceDiagram
    participant L as Leader (term 4)
    participant F1 as Follower S2
    participant F2 as Follower S3
    L->>F1: AppendEntries(index=3, term=4)
    L->>F2: AppendEntries(index=3, term=4)
    F1-->>L: success
    F2-->>L: success
    Note over L: majority (3 of 5 incl. leader) now hold index 3 from term 4, so index 3 commits, and index 2 commits transitively

Trade-offs & pitfalls

• Common wrong turn: explaining commit as majority replication, full stop. That is necessary but not sufficient; the current-term condition above is exactly what closes the gap, and is the part people skip when reciting Raft from memory.
• Followers that reject an AppendEntries because prevLogIndex or prevLogTerm do not match force the leader to step backward and retry; a purely one-at-a-time backoff is simple but slow for a follower that has fallen far behind, which is part of why snapshotting exists as an alternative catch-up path rather than only incremental backfill.
• Operational note: watching how often followers need a full InstallSnapshot, versus incremental catch-up, is a useful signal that a follower, or the network path to it, is chronically slow. This applies just as well to a Raft-backed machine learning model-metadata store as to any other Raft-based service; the underlying signal is the same regardless of what the log stores.

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.

A gossip protocol is a decentralized way for nodes to spread state (cluster membership, health, small pieces of shared metadata) by periodically picking one or a few random peers and exchanging what each side knows, the same way a rumor spreads through a population. There is no coordinator and no single point of failure: every node's job is identical, and information reaches the whole cluster in a small, predictable number of rounds even as the cluster grows large. Distributed systems reach for gossip for membership tracking and metadata propagation specifically because it scales without needing a central registry to stay in sync.

Basic mechanics

• Each node keeps a small local view of cluster state: who is alive, version numbers, small metadata.
• On a fixed interval, each node picks one or a handful of random peers and exchanges state with them, in one of three common shapes:
  • Push: a node sends its state to a random peer, unprompted.
  • Pull: a node asks a random peer for its state.
  • Push-pull: both directions in one round trip, which converges roughly twice as fast for the same message volume.
• On receipt, each side merges what it learned (for example, keeping whichever version of each entry has the higher counter) and continues gossiping on the next interval.
• This exchange is also called anti-entropy when it specifically reconciles divergent replicas rather than just spreading membership news. A well-known concrete implementation of gossip-based membership is SWIM (Scalable Weakly-consistent Infection-style process group Membership protocol), which layers a lightweight ping and acknowledgment failure-detection scheme on top of the same gossip fan-out.

Convergence: why it scales like an epidemic

Assume, as a simplifying model, that each round of push gossip roughly doubles the number of nodes that have heard a given piece of information, since every already-informed node infects one new random peer per round. Starting from one informed node, after r rounds roughly 2 to the power r nodes are informed. For the whole cluster of N nodes to be informed:

$2^r \ge N \implies r \ge \log_2 N$

For a 1,000-node cluster, log base 2 of 1000 is about 9.97, so full propagation takes on the order of 10 rounds. For a 10,000-node cluster, log base 2 of 10,000 is about 13.3, so about 14 rounds. Ten-fold-ing the cluster size only adds a handful of rounds, because the doubling model grows exponentially, not linearly, in the number of informed nodes; this is the scaling property that makes gossip viable at cluster sizes where a centralized broadcast would become a bottleneck.

Trade-offs & pitfalls

• The doubling assumption above is a simplified model (uniform random peer selection, no message loss, no adversarial behavior); real convergence is probabilistic, and pathological cases (a persistently unlucky peer-selection pattern, high churn, network partitions) can leave a minority of nodes lagging well past the expected round count.
• Load per node stays roughly constant regardless of cluster size, since each node only ever talks to a handful of peers per round, which is the actual scalability win over a centralized registry that every node would otherwise have to poll or push to directly.
• Common wrong turn: assuming gossip gives a hard, guaranteed-delivery bound. It gives a probabilistic, high-confidence bound. A system that needs a strict deadline for propagation, a security revocation for instance, usually pairs gossip with an explicit acknowledgment or a stronger consensus-backed registry for the small set of facts that truly cannot wait.

Linearizability, sequential, causal, and eventual consistency are four progressively weaker guarantees about the order in which operations on shared data appear to happen. Linearizability makes every operation look instantaneous and match real, wall-clock time. Sequential consistency drops the real-time requirement but still gives every observer the same single global order. Causal consistency only orders operations that are actually cause-and-effect related, letting unrelated operations be seen in different orders on different replicas. Eventual consistency drops ordering guarantees almost entirely and only promises that replicas converge once writes stop. Each weaker model permits more anomalies than the one above it.

Worked example: why causal consistency prevents an anomaly eventual consistency allows

Consider a social feed. Two events happen, in this order, involving the same user's friend:

1. Event P: a user publishes Post P.
2. Event C: after reading Post P, the user's friend writes Comment C, which references Post P.

Because the friend read P before writing C, C causally depends on P: P happened-before C.

• Under causal consistency, any replica that delivers C to a reader must already have delivered P to that same reader. There is no way for a client to see Comment C replying to Post P without also being able to see Post P: the system enforces the happened-before relationship on delivery.
• Under eventual consistency alone, P and C might replicate along different paths (different shards, different network routes) with no ordering guarantee between them. A reader on a lagging replica could receive C's replication packet before P's, and briefly render a comment that references a post the reader's own client cannot find yet, an orphaned reply. That is exactly the anomaly eventual consistency does not rule out and causal consistency does.

Because eventual consistency only promises the base table converges, a secondary index or materialized view (for example, a 'comments by post' index used to render the feed) can lag the base write for an unbounded window: the index might still return zero comments for Post P for some time after Comment C has already durably landed on a majority of the base replicas, since building the index from the base table's write stream is itself an eventually-consistent process, not an atomic one.

Trade-offs & pitfalls

• Common wrong turn: treating eventual consistency as one well-defined guarantee. It is really the absence of a guarantee during the convergence window, so two systems both labeled eventually consistent can behave very differently depending on how long that window typically is, and what session-level guarantees (read-your-writes, monotonic reads) are layered on top.
• Sequential consistency is rarely offered as a named product feature; it mostly shows up as an accidental byproduct of serving reads from any replica of a system that internally agrees on a single write order, without adding a real-time freshness check on the read path.
• Causal consistency requires tracking dependencies, commonly via vector clocks or similar metadata, which costs storage and complicates garbage collection, the same trade-off logical clocks introduce elsewhere in this material.
• Senior answers name the actual anomaly each model still allows, not just that it is looser. An answer that only says eventual is looser than causal, without naming a concrete permitted anomaly, is incomplete.