Distributed Systems Fundamentals Questions

Direct Answer

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

How Each Actually Reaches Agreement

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

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

Why Raft Is Easier to Implement and Reason About

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

Comparison Table

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

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

When to Still Reach for Paxos

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

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

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

Trade-offs and Pitfalls

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

Direct answer

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.

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.

Direct Answer

Clock skew is the difference between what two machines' clocks read at the same real instant. It matters because any decision that compares timestamps from different machines to decide what happened first, whether a lease is still valid, or whether a certificate is still in its valid window, quietly assumes those clocks agree, and in a real network they don't. A numerically later timestamp on one machine's clock does not reliably mean later in real time once you're comparing across machines.

Three Concrete Problems

1. Event ordering across services. If service A stamps an event with its own local clock and service B stamps a related event with its own local clock, and A's clock runs even slightly ahead of B's, an event that actually happened after (in real time) on B can end up with a numerically smaller timestamp than an earlier event on A. Anything that reconstructs what happened in what order by sorting on raw timestamps can get the sequence backwards. The same failure shows up in machine learning feature pipelines: if a feature-store write on one node happens slightly after a model-serving read on another node consumed the old value, but the writer's clock runs a bit fast, the write can carry an earlier or overlapping timestamp than the read, which corrupts any point-in-time audit of which feature value was actually used for a given prediction, if that audit trusts the raw timestamps.

2. A lease that expires early or late. Distributed locks are commonly granted as leases valid until wall-clock time T. If the holder's clock runs slow relative to the granting service's clock, the holder can believe it still owns the lease past the point the granting service has already reassigned it, expiring late from the holder's point of view and risking two nodes both acting as if they hold the resource. If the holder's clock runs fast instead, it can abandon a still-valid lease early and stop acting well before the granting service considers it expired, causing unnecessary churn.

3. A TLS (Transport Layer Security) certificate that looks valid on one node and invalid on another. Certificate validity is a wall-clock range check, evaluated locally by whichever machine happens to be doing the handshake, against the certificate's not-before and not-after dates. If one node's clock has drifted backward past the not-before date, or forward past the not-after date, that single node rejects a certificate every correctly-clocked node accepts, or the reverse, producing a confusing, node-specific TLS failure that looks like a certificate problem but is actually a clock problem.

A Concrete Trace of Why Naive Ordering Is Unsafe

Node A's clock reads 100 and Node B's clock reads 96 at the same real instant, a 4-unit skew. Event E1 happens on Node A at that instant and is stamped 100. Two time units later in real time, event E2 happens on Node B; by then B's clock reads 98 (96 plus 2), so E2 is stamped 98. Comparing the raw timestamps, 100 is greater than 98, so E1 looks like it happened after E2. But in real time, E2 actually happened after E1. Any process that orders events purely by comparing these timestamps gets the sequence exactly backwards, even though the comparison itself, 100 greater than 98, is arithmetically correct.

Why This Isn't Just a Sync-the-Clocks-Better Problem

Synchronizing physical clocks, with NTP (the Network Time Protocol) or a hardware-disciplined protocol like PTP (Precision Time Protocol), reduces the size of the skew, but it does not make comparing two independently-running clocks perfectly safe; it only shrinks the window in which the trace above can happen. The standard engineering answer for ordering that has to be correct, not just human-readable, is to stop relying on raw wall-clock comparison for that purpose and use a logical clock instead: a counter that each node increments on its own events and carries along with outgoing messages, which correctly captures which events could have influenced which others regardless of clock drift. Production distributed databases often go a step further and use a hybrid logical clock (HLC), which combines a physical-time component with a logical counter, to get correct ordering without giving up a timestamp that's still roughly readable as wall-clock time.

Trade-offs and Pitfalls

• Don't confuse clock skew, which is that two clocks disagree right now, with clock drift, the rate at which they diverge over time; skew is the instantaneous symptom you observe, drift is the ongoing cause, and a monitoring setup that only alerts on one of them will miss the other.
• A common wrong turn is assuming that running NTP means this is handled. NTP typically keeps clocks within milliseconds of each other, which is fine for human-readable log timestamps, but any nonzero skew is still a real correctness risk for anything that depends on strict ordering, so it reduces the problem rather than eliminating it.
• The lease-expiry problem specifically is best addressed by combining a conservative time-to-live with fencing at the protected resource, rejecting stale operations based on a monotonically increasing token rather than on wall-clock time at all, instead of trying to shrink clock skew to zero, which isn't achievable.

Direct answer

A checkpoint barrier is a special marker the coordinator injects into every source stream at a chosen moment. As it flows downstream mixed in with real data, each operator uses its arrival to mark a cut: everything on that input channel before the barrier belongs to checkpoint N, everything after belongs to checkpoint N+1. Once an operator has seen the barrier on all of its input channels, it takes a local snapshot of its own state and forwards the barrier onward. Because every operator's snapshot is cut at the same logical point in the data rather than the same wall-clock instant, the union of all local snapshots plus the recorded source read-positions forms one consistent global snapshot the whole job can be rewound to after a failure.

Barrier injection and alignment

The checkpoint coordinator periodically assigns an increasing checkpoint id and injects a barrier carrying that id into every source partition. Barriers travel with the data on each channel, in order, never overtaking a record. When an operator with multiple input channels receives the barrier on one channel before the others, it stops consuming further records on that channel and buffers them, while continuing to process the channels where the barrier hasn't arrived yet. This buffering-until-all-channels-caught-up step is called alignment; it guarantees the operator's eventual snapshot reflects exactly the same cut point on every input.

Local snapshot and coordinator commit

Once aligned, the operator snapshots its local state (for a keyed aggregation, the current value per key) to durable storage and forwards the barrier to its downstream operators. The coordinator marks a checkpoint complete only once every operator, all the way to the sinks, has acknowledged it, and only then persists the checkpoint's metadata as the new restore point.

Unaligned checkpoints

Alignment can add latency under backpressure or skew, since a fast channel has to wait on a slow one before the operator can snapshot. Unaligned checkpoints avoid this by not waiting at all: the framework snapshots the buffered in-flight records themselves as part of the checkpoint, alongside the operator's own state, trading more storage and I/O for lower checkpoint latency.

Worked example: barrier flow through a keyed aggregation

Job topology: Source -> Map -> KeyedSum -> Sink, with KeyedSum running as two parallel instances, A and B.

sequenceDiagram
    participant Coord as Coordinator
    participant A as KeyedSum A
    participant B as KeyedSum B
    participant Sink
    Coord->>A: barrier(42) on P0
    Coord->>A: barrier(42) on P1
    A->>A: snapshot state
    A->>Sink: forward barrier(42)
    Coord->>B: barrier(42) on P0
    Coord->>B: barrier(42) on P1
    B->>B: snapshot state
    B->>Sink: forward barrier(42)
    Sink->>Coord: ack checkpoint 42

1. Coordinator starts checkpoint 42 and injects barrier(42) into the source's two partitions, P0 at read-offset 1000 and P1 at read-offset 850.
2. Instance A receives input from both P0 and P1 after the shuffle (the keyed redistribution that routes every record for a given key consistently to the same parallel instance). barrier(42) arrives on A's P0 channel first: A stops consuming new P0 records and buffers them (alignment), while continuing to process P1 records normally, since P1's barrier hasn't arrived yet.
3. barrier(42) arrives on A's P1 channel. A has now seen the barrier on every input channel, so it snapshots its local running sums, say {key=X: 17, key=Y: 42}, to durable storage, forwards barrier(42) downstream to the Sink, and unblocks the buffered P0 records, which now belong to checkpoint 43.
4. Instance B does the same independently for its own keys.
5. The Sink receives barrier(42) from both A and B, snapshots (or, if it's a transactional sink, pre-commits) its own pending output, and acknowledges checkpoint 42 to the coordinator.
6. Once the coordinator has acknowledgements from the source (offsets P0=1000, P1=850), A, B, and the Sink, checkpoint 42 is marked complete and persisted.
7. If the job then crashes after checkpoint 42 completed but before checkpoint 43 finished, restart loads checkpoint 42: sources reset to offsets P0=1000/P1=850, A and B restore their snapshotted key-sums, and the Sink either commits its pre-committed checkpoint-42 output or relies on idempotent writes if it isn't transactional. Processing then resumes from exactly those offsets, so no record before the barrier is reprocessed and no record after it is lost.

End-to-end exactly-once needs the sink to participate

Internal exactly-once state is only as strong as what happens at the external sink. A transactional (two-phase commit, 2PC) sink pattern treats each checkpoint as a transaction boundary: during the checkpoint, the sink prepares and flushes its output but does not commit; once the coordinator marks the checkpoint complete, it tells the sink to commit. On failure, any uncommitted transaction is aborted, so restored state and committed output stay consistent. If a sink can't participate in a transaction this way (for example, one that only supports single-item idempotent writes rather than a cross-partition transaction), the fallback is idempotent writes keyed by (checkpoint_id, record_id), so the same output re-emitted after restoring from checkpoint 42 doesn't double-apply. The same barrier/snapshot mechanism underlies this regardless of what the job is computing: a change-data-capture (CDC) ingestion pipeline, a feature-computation job for machine learning, or an ordinary aggregation are all just other kinds of stateful stream jobs from the checkpoint coordinator's point of view.

Trade-offs & pitfalls

Rescaling (changing parallelism) needs a savepoint, a user-triggered durable checkpoint, plus a defined remapping of keyed state across the new number of instances. The most common pitfall is assuming "exactly-once" automatically covers the whole pipeline: if the sink isn't transactional or idempotent, restoring from a checkpoint after a crash can re-emit output that was already delivered before the crash, turning exactly-once internal state into at-least-once external effects.