Distributed Systems Fundamentals Questions

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.

Lamport clocks and vector clocks both order events in a distributed system without relying on wall-clock time, which cannot be trusted to stay synchronized across machines. A Lamport clock is a single integer per process that increases on every local event and every message received, guaranteeing that if event A happened-before event B, A's counter is smaller than B's, but not the reverse: two events can tie or land on comparable counter values without one having actually caused the other. A vector clock is a full vector, one counter per process, that lets you tell exactly whether two events are causally related or genuinely concurrent, which is the extra information a single Lamport counter throws away.

Lamport clocks

• Each process keeps one integer counter, starting at 0.
• Local event: increment own counter.
• Send: increment, then attach the counter to the message.
• Receive: set counter = max(local counter, counter in message) + 1.
• Guarantee: if A happened-before B, then LC(A) < LC(B). The converse does not hold: LC(A) < LC(B) does not imply A happened-before B.

Vector clocks

• Each process keeps a vector with one slot per process, all starting at 0.
• Local event: increment own slot.
• Send: increment own slot, attach the whole vector.
• Receive: take the element-wise maximum of the local vector and the incoming vector, then increment own slot.
• Comparison rule:

$V(A) \le V(B) \iff \forall i,\ V(A)_i \le V(B)_i \text{ and } \exists j,\ V(A)_j < V(B)_j$

• If neither V(A) <= V(B) nor V(B) <= V(A) holds, the vectors are incomparable, and the events are genuinely concurrent: no message path connects them in either direction, regardless of what wall-clock time either happened at.

Worked example: a two-person chat, printed event trace

Two people, on process P1 and process P2, are chatting. Message ordering here needs to respect causality: a reply should never appear to precede the message it replies to, which is exactly what vector clocks are for.

• e1 (P1, local event, user starts typing): Lamport clock 1, vector clock [1,0].
• e2 (P1, sends message m1 to P2): Lamport clock 2, vector clock [2,0], attached to m1.
• e3 (P2, local event, user independently opens the chat window before receiving anything from P1): Lamport clock 1, vector clock [0,1]. In real wall-clock terms, say this happens several seconds before e1 even occurs on P1's machine, since the two users' actions are completely independent at this point.
• e4 (P2, receives m1): Lamport clock = max(1, 2) + 1 = 3. Vector clock = elementwise max([0,1], [2,0]) = [2,1], then increment P2's own slot: [2,2].

Now compare e1 and e3: Lamport clocks are LC(e1)=1 and LC(e3)=1, a tie. A Lamport clock alone gives no way to tell whether these are causally related from the numbers themselves; forcing a total order would need an arbitrary tie-break, like comparing process identifiers, and that tie-break tells you nothing true about causality. The vector clocks settle it precisely: V(e1)=[1,0] and V(e3)=[0,1] are incomparable, since 1 > 0 in the first slot but 0 < 1 in the second, so e1 and e3 are concurrent by definition, even though e3 happened earlier in real wall-clock time in this scenario. Concurrency here is about the absence of a causal path, not about which one occurred first on a wall clock.

Now compare e3 and e4: V(e3)=[0,1], V(e4)=[2,2]. Every slot of V(e3) is less than or equal to the corresponding slot of V(e4), and the first slot is strictly less (0<2), so V(e3) <= V(e4), and e3 happened-before e4, correctly, since e3 and e4 both occurred on P2 in that program order.

Trade-offs & pitfalls

• Vector clocks only detect concurrency; they do not resolve it. When V(A) and V(B) are incomparable and both represent a write to the same piece of data, the vector clock correctly tells you there is a genuine conflict, but not which write should win. An application still needs a policy on top, last-write-wins by some tie-break, a CRDT merge, or surfacing both versions for a user or client to reconcile; the vector clock's job stops at detection.
• Storage cost: a vector clock needs one slot per participating process, so it grows with the number of writers, unlike a Lamport clock's single integer. Systems with many writers usually prune or cap this, for example with dotted version vectors or per-shard writer sets, rather than keep an ever-growing vector per object.
• Common wrong turn: assuming a Lamport clock's total order reflects real causality. It gives a valid total order consistent with happened-before, so if A really did happen before B, Lamport respects that, but not every pair the Lamport order ranks is actually causally related, so Lamport clock values alone cannot answer whether A caused B.

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.

You cannot verify a lock service's safety and liveness claims by code review, you have to actively try to break them. The strategy is to run the real implementation under deterministic fault injection (network partitions, message duplication, reordering, clock skew) while continuously checking two machine-checkable invariants: mutual exclusion (the protected resource never accepts conflicting grants for the same lock) and a bounded liveness guarantee (once faults stop for a stability window, some client acquires the lock within a configured bound).

Invariants worth encoding, not just asserting in prose

• Mutual exclusion: for a given lock, the set of grants the protected resource actually honors never has two simultaneously valid members.
• Fencing monotonicity: the sequence of tokens the protected resource accepts for a given lock is strictly increasing; this, not the clients' beliefs about who holds the lock, is what actually prevents a stale holder from causing damage.
• Bounded liveness: once faults stop for a configured stability window, some client successfully acquires the lock within a configured time bound.

Fault-injection scenarios that specifically target safety

• Split-brain leader ambiguity: partition the cluster so an old leader cannot reach a majority but does not yet know it, and verify the old leader alone cannot grant a lock that a legitimately elected new leader also grants.
• Duplicated and reordered messages: replay a client's earlier acquire or release message after it has already moved on, and deliver a leader's grant message after a later message from the same exchange, to check the server never re-honors a stale request.
• Clock skew: offset participant clocks up to the configured maximum tolerated skew and verify lease-expiry logic does not allow two grants to overlap.
• Sustained network flapping: repeatedly partition and heal the cluster faster than leader election converges, to check the system fails toward unavailability rather than toward a safety violation when it cannot decide cleanly.

Worked example: a fencing-token trace that catches a violation

Consider two clients, C1 and C2, and a lock L guarded by fencing tokens (a fencing token is a strictly increasing number issued with each grant that the protected resource uses to reject stale holders).

1. C1 sends acquire(L) to the current leader; the leader commits the grant through its replication log and returns token = 41 to C1.
2. A partition isolates the leader from a majority of the cluster without the leader realizing it yet (it has not stepped down).
3. The remaining majority elects a new leader, which independently commits a grant of L to C2 and returns token = 42.
4. Before the old leader detects the partition, a duplicated, delayed copy of C1's original acquire message is redelivered to it; the old leader, still believing it is in charge, replies to C1 again, appearing to reaffirm token = 41.
5. Both C1 (holding token 41) and C2 (holding token 42) now believe they hold L. This is exactly the scenario the test harness exists to surface.

The invariant check does not look at whether both clients believe they hold the lock, since that alone can be momentarily unavoidable during a partition. It looks at what the protected resource accepts: if C1 sends a write carrying token 41 after the resource has already accepted C2's token 42, the resource must reject C1's write because 41 is not greater than the highest token already seen. The test harness asserts exactly that rejection; if the resource instead accepted token 41 after token 42, that is a caught mutual-exclusion violation, because it is what the resource does, not what the clients believe, that determines whether real damage occurs.

Making this executable, not just described

• A deterministic simulation harness, or a real deployment behind a controllable network proxy (packet delay, duplication, reorder, drop, injected clock offsets), driven by scripted or randomized client operation sequences.
• Property-based generation of operation sequences plus network-event sequences, checked against the invariants after every run, so violations are found by search rather than only by scenarios a human thought to write.
• A small formal model in TLA+ (a specification language for describing an algorithm's state transitions and mechanically checking properties against them) of the same protocol, as a cheap way to explore edge cases before they are worth reproducing against the real implementation.

Trade-offs and pitfalls

Model-checking a TLA+ specification only proves the absence of the checked violations within the modeled state space and assumptions; it says nothing about the actual running code, so it complements implementation-level fault injection rather than replacing it. Tests that rely on wall-clock sleeps to sequence faults tend to be flaky in CI, since the entire point is exercising races; use logical barriers or a deterministic scheduler in the harness instead of timing. Finally, a liveness bound is only meaningful under a partial-synchrony assumption that the network eventually behaves, not as an unconditional real-time guarantee, and a test suite that leaves that assumption implicit will either flake on liveness checks during sustained chaos or silently weaken the bound until it happens to pass.

Direct answer

PACELC, short for "if Partition, Availability vs. Consistency; Else, Latency vs. Consistency", says that CAP's dilemma, choose Consistency or Availability when a network Partition is happening, is only half the story. Even when there is no partition at all, a system still has to choose between Latency and Consistency for every write it replicates, because making a write durable on every replica before acknowledging it takes longer than acknowledging it once it's durable on a single node. PACELC packages this as: if Partition occurs, trade off Availability against Consistency (exactly what CAP already says); Else, meaning no partition, trade off Latency against Consistency.

Restating CAP precisely first

CAP says that during an actual network partition, a distributed system can guarantee only one of Consistency (every read sees the latest completed write) or Availability (every request gets a non-error response) for the nodes on either side of the split, not both. A common misreading treats CAP as "pick two of three, always"; it isn't. CAP's teeth are specifically about behavior during a partition. Most systems are both consistent and available almost all of the time, precisely because a true network partition is a rare event relative to total uptime, not something happening continuously.

flowchart TD
    Start[Write occurs] --> P{Partition active?}
    P -->|Yes| AC[Choose Availability or Consistency]
    P -->|No| LC[Choose Latency or Consistency]

What PACELC adds

PACELC names the trade-off CAP is silent about: during normal operation, with no partition, you still choose between Latency (L) and Consistency (C), because synchronous replication that waits for a majority of replicas costs a round trip before it can acknowledge a write, while asynchronous or single-node-acknowledged replication returns faster but risks a reader seeing stale data, or the acknowledged write being lost outright if that one node fails before it propagates. Systems are commonly labeled by both branches together, for example PA/EL (favor Availability under partition, favor Latency otherwise, the Cassandra/Dynamo-style default) or PC/EC (favor Consistency in both cases, the HBase-style default).

Worked example: a decision with no partition occurring

A write to a piece of user data must be replicated to three nodes: R1 in the local region, and R2, R3 in two remote regions. All three are reachable; no partition is happening anywhere in this example.

• Favor consistency (the "C" side of the Else branch): the write path waits for acknowledgment from a majority, at least two of the three replicas, say R1 and R2, before returning success to the caller. Any subsequent read from a majority quorum is now guaranteed to see this write. Cost: the caller's write waits on the round trip to R2, a remote replica, even though R1, the local one, already has it durably.
• Favor latency (the "L" side of the Else branch): the write path acknowledges as soon as R1 has it durably, and replicates to R2 and R3 asynchronously in the background. Cost: the caller gets a fast, local acknowledgment, but a read served from R2 immediately afterward, before the async replication catches up, will not see the write yet. If R1 crashes before that background replication completes, the already-acknowledged write can be lost entirely, with zero partition ever occurring.

This decision, wait for two of three versus acknowledge on one, is made on every single write regardless of whether any partition is happening, which is exactly the trade-off PACELC's Else branch names and CAP alone has nothing to say about, since CAP only speaks to a system that is not fully connected.

Trade-offs & pitfalls

A common misconception is treating a database's PACELC label as a fixed law of the software rather than a description of its typical default: most systems let you tune the replication wait per request (via quorum size), so "Cassandra is PA/EL" describes its usual configuration, not something it's incapable of changing. It's also easy to blur this Else-branch trade-off with an availability discussion; in the worked example above, no node was ever unreachable, so the trade being made is purely about how long the write path waits before acknowledging, not about surviving an outage, which is a separate concern belonging to the partition branch of the theorem.