The Impossibility of Synchronized Clocks for Distributed Ordering

Hello! Welcome back to your second lesson on Distributed Systems Architecture.

In our first lesson, we identified the three defining characteristics of a distributed system: concurrency, independent failures, and the lack of a global clock. We briefly touched upon why ordering events is difficult due to network latency and clock drift.

Today, we will build directly on that foundation. This lesson focuses on the following learning outcome:

Derive why distributed systems cannot rely on synchronized physical clocks for ordering, using logical reasoning about network delays.

We will move from the high-level idea that clock synchronization is "hard" to a more rigorous understanding of why it's fundamentally impossible to achieve perfectly. This exploration will force us to abandon physical time as a reliable ordering mechanism and set the stage for the alternative: logical time.

1. The Core Problem: Timestamps vs. Causality

In a distributed system, we often want to know the order of events. For example, in a financial system, if a user requests to cancel a trade, we must know if the cancellation request happened before or after the trade was executed.

It's tempting to just put a timestamp on every event. However, this can lead to situations where the timestamps contradict the actual cause-and-effect relationship between events.

To see this in action, let's start with a very brief video.

This "inconsistency with causality" is the central problem we need to solve. To understand its roots, we must look at the physical realities of time and communication in computers.

2. The Physical Barriers to Perfect Synchronization

There are three fundamental reasons why the clocks on different computers can't be perfectly synchronized.

Let's formalize these points:

1. Finite Speed of Light: A message from London to New York takes a minimum, non-zero amount of time to travel. There is no way to communicate information instantaneously.
2. Unbounded Network Delay: The time a message takes to travel across a network is not only non-zero but also variable and unpredictable. It can be affected by network congestion, routing changes, or processing delays at switches. In our "partially synchronous" model from the last lesson, we assume delays are usually short, but we must design for the times they become arbitrarily long.
3. Clock Drift: The quartz crystal oscillators in computer clocks are physical devices. They all run at slightly different rates. Even if you could perfectly set two clocks to the same time, they would immediately start to drift apart.

These factors create a circular dependency: to measure the network delay between two nodes, you need synchronized clocks. But to synchronize the clocks, you need to know the network delay. Protocols like the Network Time Protocol (NTP) attempt to break this cycle by estimating the round-trip time and accounting for drift, but they can only guarantee that clocks are synchronized within a certain bound of error, not perfectly.

3. A Concrete Example of Failure

Let's see how these imperfections lead to incorrect system behavior. Even with NTP doing its best, small discrepancies in time can have significant consequences.

First, it's important to distinguish between the two main types of clocks available on a computer.

The example in the video is critical. Let's recap the logic:

• Machine M1 and M2 are trying to synchronize using a time-of-day clock (e.g., via NTP). Their clocks are close, but not identical.
• M1 sends a message to M2: increment x.
• The message arrives at M2. From M2's perspective, it arrives before 3:00 PM. M2 increments x to 6.
• Both machines are instructed to take a snapshot of their state at exactly 3:00 PM according to their local clock.
• M2's snapshot shows x = 6.
• M1's snapshot shows x = 5, because from its perspective, the message to M2 was sent after its local 3:00 PM had passed.

When we combine these snapshots, we get an inconsistent and nonsensical state of the world. The effect (x is 6 on M2) is visible, but its cause (the message from M1) is not visible in M1's corresponding snapshot. This is a direct result of relying on physical clocks that cannot be perfectly synchronized.

4. The Solution: A Paradigm Shift to Logical Time

If physical time is unreliable for ordering, what can we use? This question led Leslie Lamport to write one of the most influential papers in computer science. His solution was to stop trying to agree on what time it is and instead focus on agreeing on the order in which events occurred.

He proposed a new way of thinking based on causality. We can't always say when an event happened, but we can often say that event A happened before event B.

Lamport's definition of "happened before" (→) is purely logical and doesn't rely on physical clocks. It's defined by two simple rules and transitivity:

1. If events a and b happen on the same process, and a comes before b, then a → b.
2. If a is the sending of a message and b is the receipt of that same message, then a → b.
3. If a → b and b → c, then a → c.

This relation defines a partial order. It means for some pairs of events (say, a and c), we can definitively say a → c. For other pairs (say, a and d), we might not be able to say a → d or d → a. In this case, we call them concurrent.

This "happens-before" relation is the bedrock of reasoning about distributed systems. It precisely captures the flow of causality. An event a can only cause event b if a → b.

5. A Final Nuance: When Physical Clocks Still Matter

Does this mean physical clocks are useless? Not quite. A system that only uses logical ordering can still exhibit behavior that seems strange to an outside observer.

The "anomalous behavior" example is subtle but important. A user makes request A, then phones a friend who makes request B. In the real world, A happened before B. But because the "phone call" message is external to the computer system, the system might process B first.

To prevent this, we need physical clocks that are at least reasonably accurate. Lamport defines a Strong Clock Condition which says that if event a happens before b in the real world, their timestamps C(a) and C(b) should reflect that. This is what systems like Google's Spanner do with their "TrueTime" API, which uses GPS and atomic clocks to guarantee a very small bound of error on their physical clocks.

Conclusion

This lesson provided a formal derivation for why relying on synchronized physical clocks for ordering is untenable in a distributed system.

Key Takeaways:

• Perfect physical clock synchronization is impossible due to the finite speed of light, unbounded network delays, and clock drift.
• Relying on imperfect physical clocks for event ordering can lead to inconsistent and incorrect system states, where effects are observed before their causes.
• The correct approach is to shift from thinking about physical time (chronology) to logical relationships (causality).
• The "happens-before" relation provides a formal, clock-free way to define a partial order of events, capturing all potential causal relationships.
• While logical ordering is primary, reasonably synchronized physical clocks are still useful for preventing anomalies when a system interacts with the outside world.

Preview of the Next Lesson:
We've established that the natural order of events in a distributed system is a partial order, where some events are concurrent. This ambiguity is a source of great complexity. In our next lesson, we will explore different consistency models (Linearizability, Sequential Consistency, Causal Consistency, and Eventual Consistency). These models are essentially different strategies or guarantees a system can provide about how it will resolve the ambiguity of concurrent operations and present an ordered view of the world to its users.