Distributed Systems Fundamentals Questions

Direct answer

A pure Lamport clock gives causal ordering: if event a happened-before event b, its counter guarantees a's value is less than b's. But the numbers carry no relationship to real elapsed time, so you can't use them to answer "how stale is this" or "did this happen a minute ago or an hour ago." An NTP-synchronized wall clock gives a number that approximates real time, but NTP only bounds error statistically and gives zero causal guarantee: two events with a genuine happens-before relationship on different nodes can still get timestamps in the wrong order if the nodes' clocks are skewed. A hybrid logical clock (HLC) combines a physical-time component with a logical counter so it inherits the causal correctness of a Lamport clock while staying close to real time, which is why production distributed databases (CockroachDB is the standard example) use it instead of relying on either mechanism alone.

Happens-before, briefly

Event a happens-before event b if a causes b directly (same process, sequential order), or a is a message send and b is its corresponding receive, or the relation holds transitively through a chain of such steps. Two events with no such chain between them are concurrent, and no clock discussed here can tell you which one "really" happened first, because there isn't a meaningful answer to that question for concurrent events.

Pure Lamport clocks

Each process keeps an integer counter C. On a local event, C = C + 1. When sending a message, the current C is attached to it. On receiving a message carrying Cm, the process sets C = max(C, Cm) + 1. This guarantees: if a happened-before b, then C(a) < C(b). It does not guarantee the converse: C(a) < C(b) does not mean a happened-before b, since a and b could be concurrent and simply landed on different counter values by coincidence of ordering. A Lamport timestamp also has no connection to real time at all: a value of "3" tells you nothing about whether the event happened a millisecond or a year ago.

NTP-synchronized wall clocks

NTP periodically corrects a machine's local clock against a reference, keeping it within a bounded error window that is typically small on a well-run local network and considerably looser across the public internet. Two problems follow for ordering purposes: first, if two nodes' clocks are off from each other by even a small nonzero amount, a later event on a fast node can get a smaller raw timestamp than an earlier, causally-prior event on a slow node, so ordering purely by wall-clock timestamp can violate causality. Second, an NTP correction can step a machine's clock backward when it's found to be running ahead, so consecutive readings from the very same machine aren't even guaranteed to be increasing, which breaks any protocol that assumes "later timestamp means later real event" on a single node, let alone across two.

Hybrid logical clocks (HLC)

An HLC keeps a pair (pt, l): a physical-time estimate pt and a logical counter l. Update rule:

• On a local event: pt' = max(local physical clock now, pt). If pt' changed (moved forward from a fresh physical reading), reset l = 0; otherwise l = l + 1. Set (pt, l) = (pt', l).
• On sending a message: attach the current (pt, l).
• On receiving a message with (pt_m, l_m): pt' = max(local physical clock now, pt, pt_m). If pt' equals both the local pt and the message's pt_m, set l' = max(l, l_m) + 1; if it equals only one of them, take that side's l and add 1; if it equals neither (a fresh physical reading is ahead of both), reset l' = 0.
• Compare two HLC values by pt first, breaking ties with l.

Because pt is always a running maximum, it can never move backward, even if the underlying physical clock is momentarily behind or gets stepped back by an NTP correction. And because a message receive always folds in the sender's pt_m and bumps l accordingly, HLC preserves the same causal guarantee Lamport clocks give: a send always compares less than its corresponding receive.

Worked example: two nodes with skewed clocks

Node A's physical clock and node B's physical clock disagree by a few units (B is running behind A). Initialize both HLC as (pt=0, l=0).

Pure Lamport clock trace:

1. A does local event e1: Lamport(A) = 1.
2. A sends message m to B carrying Lamport = 1.
3. B does its own local event e2, concurrently, before m arrives: Lamport(B) = 1.
4. B receives m: Lamport(B) = max(1, 1) + 1 = 2. The receive event correctly shows Lamport = 2, after both e1 and e2 (each at 1). But e1 and e2 both show 1 and are genuinely concurrent; the equal values don't mean "simultaneous," they mean "no causal relationship was ever established between them," and the values give no hint whether e1 happened at real time 100 or real time 100,000.

Raw NTP-timestamp trace, same events:

1. e1 on A is stamped with A's clock reading: 100.
2. A sends m, timestamped 101 by A's clock (one tick later).
3. B's local event e2 is stamped with B's clock reading: 99 (B is running 3 units behind A for this illustration).
4. B receives m; its clock reads 100 at that moment, so the receive event is stamped 100.

Comparing raw timestamps: m was sent at A-time 101 but appears received at B-time 100, a smaller number, even though the receive must happen after the send. Ordering purely by these NTP timestamps would incorrectly conclude the receive happened before the send.

HLC trace, same events, applying the update rule above:

1. e1 on A: physical clock reads 100. pt' = max(100, 0) = 100, changed, so l = 0. HLC(e1) = (100, 0).
2. A sends m; A's clock has ticked to 101 by send time: pt' = max(101, 100) = 101, changed, l = 0. HLC(send) = (101, 0); message m carries (101, 0).
3. B's local event e2: B's clock reads 99. pt' = max(99, 0) = 99, changed, l = 0. HLC(e2) = (99, 0).
4. B receives m=(101,0); B's own physical clock reads 100 at that moment. Apply the receive rule: pt' = max(100, 99, 101) = 101. Since pt' equals the message's pt_m (101) but not B's own pt (99) or the local physical reading (100), l' = l_m + 1 = 0 + 1 = 1. HLC(receive) = (101, 1).

Result: HLC(receive) = (101, 1) compares greater than HLC(send) = (101, 0), correctly ordering receive after send, even though B's own physical clock (100) was behind A's send-time clock (101). The HLC borrowed A's physical time component through the max() step specifically to preserve this ordering, which the raw NTP-timestamp comparison above could not do. And the HLC's physical component, 101, stays in the same real-time neighborhood as both clocks (99-101), unlike a pure Lamport counter, which would have produced something like "3" with no relationship to real time at all.

What HLC gives you that neither gives alone

1. Monotonicity even when the underlying physical clock runs behind or is stepped backward by an NTP correction, because the pt component is a running maximum that only ever advances.
2. The same happens-before guarantee Lamport clocks give, since a message receive always compares greater than its corresponding send.
3. A value that stays close to real wall-clock time, which lets you do things a pure Lamport counter cannot: read "as of physical time roughly T", size a lease's expiry in real seconds, or meaningfully compare timestamps from two nodes that never directly exchanged a message. Two Lamport clocks that never communicated are not comparable in any useful sense, since Lamport's ordering guarantee only holds across a causal chain; two HLCs that never communicated still each track real elapsed time, so they remain approximately comparable.

Leases and distributed coordination

A lease grants a component an exclusive right to act until an expiry, and that expiry check has to survive the granting node's physical clock moving. If a lease's expiry were checked against a raw NTP-disciplined wall clock, a backward correction on that clock could make an already-expired lease look valid again. Because HLC's physical component only advances, timestamps derived from it never regress even if the underlying physical clock momentarily does, which is why HLC (or something with the same monotonicity property) is the safer building block underneath lease-based coordination than a raw wall clock.

Trade-offs & pitfalls

A common trap is reading Lamport(a) < Lamport(b) as "a happened first" when a and b are actually concurrent; the clock never promised that. Another is assuming HLC removes the need for a synchronized physical clock entirely: HLC's pt component is still fed by the same underlying, NTP-disciplined system clock, so gross clock error still degrades how close HLC stays to real time. HLC protects the ordering and monotonicity guarantees from that error; it doesn't eliminate the error itself.

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.

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.

At a handful of nodes a fixed heartbeat timeout works fine: miss N beats, declare the node down. At several thousand nodes spread across racks and regions, the same fixed threshold produces both false positives (a node under scheduling pressure or behind a congested link gets marked down while still alive) and slow true detections (a threshold loose enough to avoid those false positives takes too long to catch a real failure), because network and scheduling jitter is not uniform across the cluster. A Phi Accrual failure detector replaces the single global timeout with a statistical model of each node's own recent heartbeat behavior, so the question becomes how improbable this silence is given what has actually been observed from that specific node, rather than whether more than T seconds have passed, and it outputs a continuously increasing suspicion level, phi, instead of a binary up-or-down verdict.

Membership and probing, before the suspicion model

• Partial views and gossip: each node keeps a small, mostly random subset of the membership rather than the full list, and periodically gossips membership updates and heartbeats to a few random peers, so state propagation stays cheap instead of all-to-all.
• Direct and indirect probing (SWIM-style; SWIM: a gossip-based membership protocol combining direct pings with an indirect fallback): a node pings a random peer directly, and if it gets no acknowledgment, asks a handful of other random members to ping that peer on its behalf, since one lossy path between two specific nodes should not be read as evidence the target itself is down.
• A minimal membership-manager state machine per monitored node: ALIVE, SUSPECT, DEAD. Failed direct-plus-indirect probes move a node from ALIVE to SUSPECT rather than straight to DEAD, and the suspicion is gossiped with an incarnation number, so a node that is actually alive can refute it by re-announcing itself with a higher incarnation before it is declared DEAD and dropped from membership.

From a binary probe result to a continuous suspicion level

Probing only tells you whether a heartbeat arrived, which is still binary. Phi accrual sits on top of that: instead of one global timeout, each node keeps a short sliding window of the actual inter-arrival times it has observed from a given peer, uses that history to estimate how spread out that peer's heartbeats normally are, and converts the elapsed time since the last heartbeat into a suspicion level using roughly:

$$\phi(t) = -\log_{10}\big(P_{later}(t)\big)$$

where $P_{later}(t)$ is the estimated probability, given that peer's own recent history, that a heartbeat still arrives more than $t$ time units after the previous one. As $t$ grows past what the peer's history says is normal, $P_{later}(t)$ shrinks and phi grows smoothly and without bound, instead of snapping from 0 to 1 at one fixed cutoff.

Why this matters at thousands of nodes: a peer on a congested cross-region link naturally has wider jitter in its own history, so it takes a longer silence to reach the same phi value as a peer on a quiet local link, without anyone hand-tuning a per-peer timeout. It also lets different consumers of the same signal act at different confidence levels: something that only needs to stop routing traffic to a possibly-dead node can act at a low phi and cheaply reverse course if the node turns out fine, while something that removes a node from a lock's quorum permanently can wait for a much higher phi, all from the same underlying measurement.

Worked example: computing phi from a pinned heartbeat history

Take a 6-sample sliding window of observed inter-arrival times, in milliseconds, for one peer: [1000, 1300, 700, 1100, 900, 1200].

Mean $\mu = 1033.33$ ms, population standard deviation $\sigma = 197.2$ ms.

Approximating the interval distribution as Normal($\mu, \sigma^2$), so that $P_{later}(t) = \tfrac{1}{2}\,\mathrm{erfc}\!\left(\tfrac{t-\mu}{\sigma\sqrt{2}}\right)$ (erfc is the complementary error function, a standard tool for turning a distance from the mean into the probability mass remaining in the distribution's tail beyond that point), gives:

Tracing the 1500 ms row end to end: standardize the elapsed time against this peer's own mean and spread, $z = (1500 - 1033.33) / (197.2 \times \sqrt{2}) = 466.67 / 278.88 \approx 1.673$; convert that into a tail probability, $P_{later}(1500) = \tfrac{1}{2}\,\mathrm{erfc}(1.673) \approx \tfrac{1}{2} \times 0.0180 \approx 0.00898$; then take $-\log_{10}$ of that probability, $\phi(1500) = -\log_{10}(0.00898) \approx 2.05$. The other three rows fall out of the same three steps with a different elapsed time plugged in.

At t = 1000 ms, right around this peer's own mean, phi stays near zero: nothing unusual. At t = 1500 ms, phi crosses 2, a mild anomaly worth noting but not worth acting on for most purposes. By t = 2500 ms, phi is in the double digits, meaning the observed silence is astronomically improbable given this specific peer's recent behavior, which is enough statistical confidence for even a conservative consumer to move the node to SUSPECT, or to DEAD if it was already SUSPECT and never refuted with a higher incarnation.

Trade-offs and pitfalls

Phi is not a probability itself, it is a log-scaled confidence score, and reading a given phi value as a direct percentage chance of failure is a common misunderstanding; the number only means something relative to whatever threshold a given consumer chooses. A second pitfall is picking one global phi threshold across a heterogeneous fleet, which reintroduces the exact problem this design was meant to solve, since the entire benefit comes from calibrating to each peer's own recent history rather than from a smarter constant. Third, phi accrual detects the absence of a heartbeat; it cannot distinguish a genuinely dead node from a network partition dropping every packet between two specific nodes while both are alive and healthy elsewhere, so membership decisions that need to be safe, like removing a node from a lock's quorum, still need a consensus-backed or fencing mechanism layered on top of the suspicion signal, not phi alone.

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.