Distributed Systems Fundamentals Questions

Direct Answer

The CAP theorem says a distributed system that can be split by a network partition can only guarantee two of three properties at once: Consistency, Availability, and Partition tolerance. Because real networks do partition (links fail, messages get delayed or dropped), partition tolerance isn't really an optional design choice, so the actual trade-off every replicated system makes, and only makes while a partition is actually happening, is between Consistency and Availability.

What Each Property Guarantees

• Consistency (C): every read returns the result of the most recent completed write, as if there were only one copy of the data (this is the strong, linearizable notion of consistency).
• Availability (A): every request that reaches a non-failed node gets a response, without a guarantee that the response reflects the latest write.
• Partition tolerance (P): the system keeps operating even when the network drops or delays messages between nodes, splitting them into groups that can't talk to each other.

Why You Only Get Two, and Only During a Partition

When there is no partition, a well-built system can offer both C and A: every node can talk to every other node, so it can confirm it has the latest data before answering. The theorem only bites once a partition actually separates the cluster into two or more groups. At that point, a node in the minority (or either side, in a symmetric split) that receives a request has exactly two choices:

• Answer immediately with whatever data it has locally. That satisfies Availability, but the data might be stale relative to a write that landed on the other side of the partition, so it does not satisfy strong Consistency.
• Refuse to answer (return an error or block) until it can confirm it isn't giving out stale data, typically by waiting for the partition to heal or for enough of the cluster to be reachable. That satisfies Consistency, but it fails Availability for that request.

There is no third option that gives both while the partition is open. That is the entire content of the theorem: it's about behavior during the partition window, not a permanent label on a system.

CP and AP Examples

• A CP-leaning example: a consensus-backed coordination store, such as etcd (a distributed key-value store built on the Raft consensus protocol). If a partition isolates a minority of nodes from the quorum, that minority stops serving both reads and writes rather than risk returning stale or conflicting data. It gives up availability on the minority side to preserve strong consistency everywhere it does respond.
• An AP-leaning example: a Dynamo-style, eventually-consistent key-value store. During a partition, every reachable node keeps accepting reads and writes on both sides, so the system stays available, but the two sides can accumulate divergent writes that must be reconciled once the partition heals (via version vectors, last-write-wins, or application-level merge logic). It gives up guaranteed-fresh reads to preserve availability.

CAP's "Consistency" vs. ACID's "Consistency"

These are two different axes, and conflating them is a common interview trap. ACID (atomicity, consistency, isolation, durability) describes properties of a single transaction, typically on one database: its "C" means a transaction only ever moves the database from one state that satisfies its own defined invariants (foreign keys, uniqueness constraints, application-level rules) to another such state. It says nothing about how fresh a read on a different replica is.

CAP's "C" is about replication: whether a read anywhere in the system reflects the most recent completed write, regardless of which physical replica served it. A system can be perfectly ACID-consistent (every transaction respects its constraints) on every individual replica while still being CAP-inconsistent overall, because a stale replica can return an old value that was, at the time it was written, a perfectly valid state.

Trade-offs and Common Pitfalls

• Treating CAP as a fixed label for an entire system is a common misreading. The choice is scoped to a partition and can even be scoped per operation: a single system can serve some requests (say, checkout) with a CP posture and others (say, product-view counts) with an AP posture.
• Don't assume "P" is a design choice you can decline. Every distributed system that spans more than one process over a real network needs to survive partial network failure, so the honest framing is which of C or A you give up when partitioned, not whether to support partition tolerance.
• A frequent good follow-up is PACELC, which asks what you trade off between latency and consistency even when there is no partition happening, since CAP alone is silent about that normal-operation case.

A CRDT (Conflict-free Replicated Data Type) is a data structure whose update and merge operations are mathematically guaranteed to make every replica converge to the same value, with no locking, coordination, or central authority, as long as every update eventually reaches every replica. State-based CRDTs ship the whole replica state and merge it with a commutative, associative, idempotent join function; operation-based CRDTs ship individual operations that must themselves be commutative and be delivered with causal ordering. A grow-only counter (G-Counter) and an observed-remove set (OR-Set) are the two simplest concrete examples of this guarantee in action.

Why convergence is guaranteed

Convergence works because the merge operation is commutative (order doesn't matter), associative (grouping doesn't matter), and idempotent (merging a state with itself changes nothing), so applying merges in any order, any number of times, produces the same final state. Formally, this kind of merge is called a join, and a replica's state is modeled as an element of a join-semilattice: a partially ordered set where the join always computes the least upper bound of two states. That is the actual property behind convergence without coordination: it is not that conflicts never happen, it is that the merge function is defined so a conflict has exactly one well-defined resolution no matter how or when it gets computed.

G-Counter (grow-only counter)

• State: a vector with one non-negative integer slot per replica, c[i].
• Local update: a replica only ever increments its own slot.
• Merge: element-wise maximum across the two vectors.

$c'[i] = \max(c_1[i], c_2[i])$

• Read: sum across all slots.

$\text{total} = \sum_{i} c[i]$

• Because each slot only ever grows for its own replica, taking the max per slot can never lose an increment either side already recorded.

OR-Set (observed-remove set)

• State: a set of (element, unique tag) pairs, split into an add-set and a remove-set of tags.
• Add(e): mint a fresh tag, insert (e, tag) into the add-set.
• Remove(e): copy every tag currently observed for e into the remove-set; it removes only tags this replica has actually seen, never tags added elsewhere that haven't arrived yet.
• Merge: union the add-sets, union the remove-sets.
• An element counts as present if it has at least one tag in the add-set that is not in the remove-set.

Naming the comparators explicitly

Worked example: G-Counter convergence

Three replicas A, B, C start at (0,0,0):

• Replica A processes 2 local increments: its state becomes (2,0,0).
• Replica B processes 3 local increments, concurrently, before hearing from A: (0,3,0).
• Replica C stays idle: (0,0,0).

A and B exchange state and merge (element-wise max): merge((2,0,0),(0,3,0)) = (2,3,0). Read = 2+3+0 = 5. C later merges with that result: merge((0,0,0),(2,3,0)) = (2,3,0). Read = 5. Whichever order the three replicas merge in, the final vector is (2,3,0) and the read is 5, exactly matching the 2+3=5 real increments actually performed. No increment is lost and none is double-counted.

Worked example: OR-Set add and remove race

Replicas R1 and R2 have already converged on a set containing 'milk' with tag t1. The two replicas are then partitioned from each other:

• R1's user removes 'milk': remove-set gains {t1}, the only tag R1 has ever observed for 'milk'.
• R2's user, unaware of the removal, re-adds 'milk': add-set gains a brand-new tag {t2}, so the add-set is now {t1, t2}.

On merge: add-set = {t1, t2} (union), remove-set = {t1} (union). 'milk' is present because t2 is in the add-set and not in the remove-set. This is the correct outcome: R2's re-add introduced a tag the remover never saw, so it survives, exactly the observed-remove semantics the name describes.

Trade-offs & pitfalls

• Storage and bandwidth: every element needs extra metadata (a vector slot per replica for counters, a unique tag per add for sets), and removed elements don't disappear until a garbage-collection pass establishes causal stability across replicas.
• The edge case that catches teams out: CRDTs don't compose across non-commutative operations. A G-Counter or OR-Set is safe because the operations that define it (increment, tagged add and remove) are commutative by construction. But if you build an append-only log CRDT and then bolt on an application-level 'delete the last 3 entries' operation defined by position, that composition is not well-defined under concurrency: 'last 3' means something different on each replica depending on how many entries have been concurrently appended there at the time the delete runs, so two replicas can end up deleting different entries even though each individually applied a correct-looking CRDT merge. The fix is the principle OR-Set already uses: target deletions by a stable element identifier, never by position or count.
• When to avoid: anywhere a global invariant spans multiple keys (uniqueness, a balance that must never go negative), or the business logic genuinely isn't commutative. CRDTs solve convergence, not arbitrary correctness.

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

A saga coordinates a business transaction that spans multiple services by breaking it into a sequence of local transactions. Each service commits its own step immediately with no cross-service lock held, and if a later step fails, the saga undoes the steps that already succeeded by running a compensating action for each one, in reverse order. This trades strict, all-or-nothing atomicity for eventual, recoverable consistency and loose coupling between services.

Choreography vs. Orchestration

• Orchestration: a central coordinator issues each step as a command to the relevant service and decides, based on that service's response, what to do next, including which compensations to trigger if something fails. The whole workflow lives in one place, which makes it easier to see, test, and reason about end to end.
• Choreography: there is no central coordinator; each service publishes an event when it finishes its local step, and whichever service is subscribed to that event reacts by doing its own step and publishing its own event in turn. This avoids coupling every service to a central coordinator's command contract, but it scatters the workflow logic across services, so understanding or changing the whole sequence means tracing through several services' event subscriptions instead of reading one place.

Worked Trace: Order Fulfillment When Shipment Fails (Orchestration Style)

Order O123, three steps: reserve inventory, charge payment, schedule shipment.

1. Orchestrator sends ReserveInventory(O123, sku=42, qty=1) to Inventory. Inventory reserves the unit and replies Reserved.
2. Orchestrator sends ChargePayment(O123, $50) to Payment. Payment captures the charge and replies Charged.
3. Orchestrator sends ScheduleShipment(O123) to Shipping. Shipping tries to allocate a carrier slot and replies Failed: no carrier capacity.
4. The orchestrator now runs compensations in reverse order. It sends RefundPayment(O123, $50) to Payment, undoing step 2. Payment replies Refunded.
5. It sends ReleaseReservation(O123, sku=42, qty=1) to Inventory, undoing step 1. Inventory replies Released.
6. The orchestrator marks order O123 as Failed and notifies the customer.

The same sequence in choreography looks like this instead: Inventory reserves and emits InventoryReserved(O123). Payment, subscribed to that event, charges and emits PaymentCharged(O123). Shipping, subscribed to PaymentCharged, tries to schedule and, on failure, emits ShipmentFailed(O123). Both Payment and Inventory are subscribed to ShipmentFailed: Payment independently issues its own refund and emits PaymentRefunded(O123), and Inventory independently releases its reservation and emits ReservationReleased(O123). No single component ever holds the full picture of the workflow; each service only knows what to do when it sees an event it's subscribed to.

Trade-offs and Pitfalls

• Every forward step and every compensating action has to tolerate being retried, since at-least-once delivery means ChargePayment could be delivered twice; this is a system-property requirement on the saga's steps, a separate concern from how an external API exposes idempotency to its own callers.
• The saga's state, meaning which steps have completed and which compensations are pending, needs to be durably persisted, whether by a central orchestrator or by each participant in a choreography, so that a crash and restart can resume the saga correctly instead of leaving it stuck partway.
• Not every action has a true inverse. Compensating a shipment step after the package has physically left the warehouse can't undo the physical fact, only correct the system's record and possibly trigger a real-world return process; a senior design puts the hardest-to-compensate steps as late as possible in the sequence.
• Choose a saga when the steps naturally live in separate services or databases and each one can be given a real, working compensating action. Reach for a real distributed transaction only when an intermediate, partially-applied state genuinely cannot be tolerated and you can afford a synchronous locking protocol across every participant, which a saga specifically avoids.

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.