Distributed Systems Fundamentals Questions

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.

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.

Direct Answer

A distributed lock service has to guarantee that, at any real instant, at most one live client believes it safely holds the lock, and it has to keep making that guarantee even when a client crashes mid-hold or the network delays messages. The safest way to build one is on top of something that already solves distributed agreement (a consensus protocol with a majority quorum), because a lock without a canonical ordering source can end up with two clients each convinced they're the holder.

Comparing Three Implementations

Fencing Tokens: Why a Lease Alone Isn't Safe

A lease with a time-to-live tells you how long to wait before you're allowed to consider a holder dead, but it can't stop a holder that is still alive, just delayed, from acting after its lease has actually expired. A process pause (for example, a stop-the-world garbage collection pause) or a delayed network write can make a client believe it still holds the lock long after the lock service has moved on.

Fencing tokens close this gap. Every successful lock grant returns a monotonically increasing number (the fencing token). The client includes that token with every operation it performs against the protected resource. The resource itself, not just the lock service, tracks the highest token it has ever seen and rejects any operation carrying a lower one.

sequenceDiagram
    participant A as Client A
    participant B as Client B
    participant L as Lock Service
    participant R as Protected Resource
    A->>L: Acquire lock
    L-->>A: Granted, token = 34
    Note over A: Long garbage collection pause, exceeds the lease TTL
    L->>L: Lease expires, lock released
    B->>L: Acquire lock
    L-->>B: Granted, token = 35
    B->>R: Write(token = 35)
    R-->>B: Accepted, 35 is higher than any token seen so far
    A->>R: Write(token = 34)
    R-->>A: Rejected, 34 is lower than the last accepted token 35

Concretely: suppose the lease time-to-live is configured to 10 seconds. Client A acquires the lock and gets token 34, then falls into a garbage collection pause longer than that window. The lock service, seeing no renewal, expires A's lease and grants the lock to client B with token 35. B writes to the resource with token 35; the resource records 35 as the highest token seen. A wakes up, still believing it holds the lock since it has no way to know time passed, and sends its own write carrying its old token, 34. Because 34 is lower than the 35 the resource already recorded, the resource rejects A's write. The stale holder is blocked from doing damage even though the lock service itself never directly told A it lost the lock.

Lease-Based Locking vs. Optimistic Concurrency

Not every coordination problem needs an actual lock. A lease is a pessimistic mechanism: it reserves exclusive access for a time window whether or not anyone else is actually trying to touch the resource, and it inherits all the lease-renewal and clock-skew risk described above. An alternative for many single-resource coordination problems is optimistic concurrency control: read the resource's current version, compute the intended change, and write it back with a compare-and-swap that only succeeds if the version hasn't changed since the read. This sidesteps lease renewal and clock skew entirely, since there's no time window to defend, but it means contending clients retry instead of queueing, which gets expensive under high contention.

As a rule of thumb: prefer optimistic compare-and-swap when you're coordinating a single write to a single record and can express the whole operation as one atomic check-and-set. Reach for a real lock or lease when the critical section spans multiple steps or has side effects outside the data store itself, such as kicking off a batch job or calling an external system, that can't be rolled into one atomic compare-and-swap.

Trade-offs and Pitfalls

• A lock service alone, without fencing enforced at the resource, is not actually safe: the resource has to participate in validating tokens, or a stale holder's writes go through unchallenged.
• The well-known Redlock (multi-instance Redis locking) design has been criticized for relying on synchronized clocks and not accounting for pauses like the one in the worked example; that critique is really an argument for fencing tokens as the real safety mechanism, with the lease itself only providing liveness (bounding how long you wait before treating a holder as dead), not safety.
• A lease time-to-live that's too short causes unnecessary churn under normal jitter; one that's too long makes real crashes take longer to recover from. Neither extreme removes the need for fencing tokens at the resource.
• Single-primary database row locks scale the worst across regions and don't survive a failover cleanly unless the failover procedure is specifically built to carry the lock state or invalidate it.

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.

Direct Answer

In a system with N replicas, a write is only considered committed once W of those replicas have acknowledged it, and a read is only considered complete once R replicas have been queried and the freshest value among their answers is returned. If you pick W and R so that

then every possible set of W replicas and every possible set of R replicas are guaranteed to overlap in at least one replica, which means any read is guaranteed to touch at least one replica that has the most recent write.

Why the Overlap Guarantee Holds

This falls out of a simple counting fact: if you pick two subsets of a set of N items, and the sizes of those two subsets add up to more than N, they cannot be disjoint. If a write-set of size W and a read-set of size R were completely disjoint, sharing no replica at all, together they would use W + R distinct replicas out of only N available, which is impossible once W + R > N. So the two sets must share at least one replica, and since the write-set includes every replica the write reached, the shared replica is guaranteed to have seen the latest write.

Worked Example, N = 5

Take five replicas, labeled 1 through 5. Choose W = 3 and R = 3 (3 + 3 = 6 > 5, so the guarantee holds).

A write commits to replicas {1, 2, 3}, the write quorum. A later read queries replicas {3, 4, 5}, the read quorum. The overlap between {1, 2, 3} and {3, 4, 5} is {3}, so replica 3 is guaranteed to be in both sets, and since replica 3 has the latest write, the read correctly returns the fresh value even though replicas 4 and 5 are still stale.

Now see what happens if you drop below the threshold: keep W = 3 but use R = 2 (3 + 2 = 5, not greater than N = 5, so the guarantee no longer holds). A read that happens to query {4, 5} shares no replica at all with the write quorum {1, 2, 3} and would return the stale value those two replicas still hold, with no way for the client to know it missed the latest write.

Trading Off Latency, Availability, and Durability

• Lowering W speeds up writes, since fewer replicas have to acknowledge, and lets writes succeed even if more replicas are down, but it weakens durability (fewer copies exist right after the write) and forces R to be larger to keep W + R > N, which slows reads down instead.
• Lowering R speeds up reads the same way, at the cost of needing a larger W.
• To keep serving at a chosen W or R while tolerating f replica failures, you need enough surviving replicas to still form that quorum, so majority quorums, such as W = R = 3 for N = 5 (the smallest quorum size bigger than half of 5), are a common default: they satisfy W + R > N for any N, and they keep working as long as a majority of replicas are reachable.

Leaderless Quorums vs. a Leader-Based Design

Quorum systems like this are naturally leaderless: any client can attempt a write or a read against any W or R replicas without funneling through one elected coordinator, unlike a Raft-based design where every write has to go through the single current leader. That gives quorum systems more availability during a partition, since any reachable set of W or R replicas can keep working, at the cost of needing real conflict handling: two writes that each reach a different, overlapping-but-not-identical set of replicas can produce concurrent versions that a read has to reconcile, by comparing versions and taking the latest or surfacing both to the application, which a single-leader system avoids by construction since all writes are already serialized through the leader.

Choosing Sane Defaults in a Client Library

A client library that exposes N, R, and W as tunable knobs should default to a majority quorum on both sides, W = R = the smallest integer greater than N / 2, rather than exposing the raw numbers with no guidance, because majority-on-both-sides is the smallest configuration that always satisfies W + R > N regardless of N, and it gives a reasonable latency-versus-safety balance without requiring the caller to re-derive the inequality themselves. The library should still let advanced callers override it, such as R = 1 for the fastest possible read when the caller is prepared to handle occasional staleness itself, or W = N for maximum durability when the caller can tolerate slower writes, with the safety trade-off documented at each override.

Trade-offs and Pitfalls

• Quorum overlap guarantees that a read touches at least one replica with the latest write; it does not by itself guarantee the read correctly identifies which of the R responses is the latest one. Without comparing versions or timestamps correctly across the R responses, you can still return a stale value even though the fresh one was right there in the response set.
• Concurrent writes are a real gap: if two writes race and land on different, only-partially-overlapping write quorums, you can end up with genuinely concurrent versions that need reconciliation, not just staleness that time will fix.
• Picking W = 1 to maximize write availability forces R = N to keep the safety guarantee, which makes every read fragile to a single unavailable replica; it's rarely a good default outside very read-light, write-heavy workloads that can tolerate that risk.