Time in Distributed Systems

When an application runs on a single server, it is easy to tell the order of events.

The server’s clock gives a clear timeline. However, when an application runs on multiple servers in different locations, this becomes challenging. For example, imagine two friends sending messages in a chat app simultaneously. How can the system decide which message should appear first?

Relying solely on the local clocks of machines is not a safe approach.

Network delays and inaccurate clocks can cause errors, such as messages appearing in the wrong order or even data being lost. Ensuring events are ordered correctly is one of the primary challenges in distributed System Design.

To solve this, we do not depend only on physical time. Instead, we use logical time, which tracks the order of events across the system rather than relying on wall-clock time.

Why is time challenging in distributed systems?

In a distributed system, there is no single source of truth for time.

Each computer, or node, has its own local clock. While protocols like the Network Time Protocol (NTP)https://www.ntp.org/ attempt to keep these clocks synchronized, achieving perfect accuracy is impossible. This discrepancy creates several fundamental challenges.

The primary issues that complicate time synchronization include:

• Network latency: The time it takes for a message to travel from one node to another is variable and unpredictable. For example, a message sent at 10 o’clock might reach its destination half a second later or even a full second later, depending on network conditions.

• Clock drift: Physical clocks on different machines run at slightly different rates. Over time, even clocks that were once synchronized will drift apart. A few milliseconds of drift per hour can accumulate quickly, resulting in significant discrepancies.

• Unreliable synchronization: Clock synchronization mechanisms can fail or introduce their own delays, making it unsafe to assume that all nodes share the same view of time.

These challenges directly impact a system’s ability to maintain consistency, coordinate actions between nodes, and debug problems.

For instance, if two nodes process conflicting updates, the system must have a way to decide which update occurred first. Without a reliable global clock, this decision becomes ambiguous. The following diagram illustrates how, in distributed systems, clock skewThe difference in time readings between two clocks that are supposed to be synchronized. can make it impossible to use local timestamps to determine the true order of events.

To overcome these physical limitations, engineers developed logical clocks, which focus on the order in which events happen relative to each other, rather than depending on each node’s local clock to timestamp events.

Logical clocks and event ordering

Because local clocks cannot be fully trusted to order events accurately in a distributed system, we need an alternative mechanism.

Logical clocks offer a way to reason about event ordering without relying on a shared, synchronized physical clock. A logical clock assigns a timestamp—a simple numerical value—to each event. This number does not represent real-world time; instead, it captures the logical sequence of events, indicating which events happened before or after others in the system.

For example, if event a occurs first, it might receive the timestamp 1, event b might receive 2, and so on.

By comparing these logical timestamps, a distributed system can establish a consistent global ordering of events, even when those events occur on different machines with unsynchronized clocks. Logical clocks provide a foundational tool for reasoning about causality and are implemented in algorithms such as Lamport clocks, which we will explore in the next section.

The Lamport clock algorithm

The Lamport clock, created by Leslie Lamport, is a concrete algorithm for implementing logical clocks.

It assigns a logical timestamp to every event in a distributed system, allowing events occurring on different machines to be ordered consistently across the system. In a distributed system, many operations run simultaneously across multiple machines (or nodes).

On each node, operations are grouped into processes, each producing its own sequence of events. The Lamport clock algorithm assigns each process its own logical clock, which is used to timestamp events and align them into a consistent global order.

The key principle for ordering events is the happened-before relationship, written as a → b. This relationship captures causal ordering: event a is considered to have influenced or happened-before event b if one of the following holds:

1. Events a and b occur in the same process, and a happens before b in that process’s sequence of events.

2. Event a is the sending of a message from one process, and event b is the receipt of that message by another process.

3. There is an event c such that a happened before c, and c happened before b. (transitivity).

The happened-before relationship creates a type of ordering called a partial order. This means it can determine the order of events only when there is a causal link between them. For events in separate processes with no causal connection (known as concurrent or independent events), the system cannot determine which occurred first.

The Lamport clock algorithm follows three simple rules for updating each process’s logical clock:

1. Before a process executes an event (such as a local computation or sending a message), it increments its clock by one.

2. When a process sends a message, it includes its current clock value (the Lamport timestamp) in the message.

3. When a process receives a message, it updates its local clock to:

The slides below illustrate how the Lamport clock algorithm updates the logical clocks of two processes, P1 and P2.

The Lamport clock algorithm guarantees that if an event a happens-before an event b (denoted as a → b), then the Lamport timestamp of a will be less than that of b, i.e., as C(a) < C(b). This property helps maintain a consistent ordering of causally related events across the distributed system.

For example, in slides 5 and 6 above, the event in process P1 with Lamport timestamp 3 sends a message to process P2, which leads to an event with Lamport timestamp 4. Since message sending implies a causal relationship (i.e., the send event happens-before the receive event), the Lamport timestamps correctly reflect this ordering: 3 < 4.

However, it is important to note that the converse is not true: if C(a) < C(b), we cannot conclude that events a and b are causally related (i.e., a → b).

This limitation becomes clear in another example from slide 3 above: the event in process P1 with Lamport timestamp 1 occurs independently of the event in process P2 with timestamp 2. Although the timestamp of one event is less than that of the other (1 < 2), there is no causal relation between these events.

Consequently, the Lamport clock algorithm cannot determine whether two events are causally related or concurrent.

In other words, while the algorithm captures causality, it cannot distinguish it from concurrency, which may lead to incorrect assumptions about the order of independent events.

This limitation motivated the development of more advanced mechanisms, like the vector clock, which can differentiate between causally related and concurrent events.

The vector clock algorithm

The vector clock algorithm was developed to overcome a key limitation of the Lamport clock algorithm: its inability to distinguish between causal and concurrent events.

Unlike the Lamport clock, the vector clock algorithm enables a system to determine not only the order of events but also whether event a causally precedes event b (a → b) or if the two events occur concurrently. To achieve this, instead of a single logical clock like the Lamport clock algorithm, each process i maintains a vector clock (an array of integers), VC(i), with a size equal to the total number of processes (N) in the system.

Each entry VC(i)[j] records the timestamp of the latest event in the process j that process i has recorded.

This is how the algorithm updates the vector clocks:

1. In the beginning, each process’s vector clock is initialized with all entries set to zero.

2. Before a process i executes a local event, it increments its own component in its vector clock: VC(i)[i] = VC(i)[i] + 1.

3. When process i sends a message to process j, it attaches its entire vector clock VC(i).

4. When process j receives a message from the process i containing VC(i), it first updates its own vector clock by taking the element-wise maximum of the two vectors: VC(j)[k] = max(VC(j)[k], VC(i)[k]) for all k. Then process j increments its own component to reflect the receipt of the event: VC(j)[j] = VC(j)[j] + 1.

The slides below illustrate how the vector clock algorithm updates the vector clocks of two processes, P0 and P1.

With vector clocks, we can precisely determine the causal relationship between any two events, a and b.

Event a is said to have happened-before b if and only if the vector timestamp of a has all elements less than or equal to the corresponding elements in the vector timestamp of b, and at least one element is strictly less. For example, in slide 6 above, the event in process P0 with vector timestamp [3, 0] happened-before the event in process P1 with vector timestamp [3, 3], because:

• Every element in [3, 0] is less than or equal to the corresponding element in [3, 3], and

• The second element is strictly less (0 < 3).

On the other hand, the events are considered concurrent if some elements in a’s timestamp are greater than the corresponding elemets in b’s, while others are smaller. For example, in slide 3 above, the event in process P0 with vector timestamp [1, 0] and the event in process P1 with vector timestamp [0, 2] are concurrent because:

• The first element in [1, 0] is greater than in [0, 2] (1 > 0),

• While the second element is smaller (0 < 2).

This capability is vital in eventually consistent data stores such as Amazon’s DynamoDBhttps://aws.amazon.com/dynamodb/ or Riakhttps://riak.com/index.html to detect and resolve write conflicts.

While ordering individual events is critical, sometimes we need a broader view of the system’s state at a single logical point in time. This leads us to the distributed snapshot problem.

Consistent state and the distributed snapshot problem

Beyond ordering individual events, a common requirement in distributed systems is to capture a globally consistent state of the entire system at a specific moment in time.

This is known as a distributed snapshotA recording of the global state of a distributed system, including the state of each process and the messages in transit between them, that is consistent with causality.. Such a snapshot is invaluable for debugging, checkpointing for fault tolerance, and garbage collection. The primary challenge is that there is no single moment in time when we can pause the entire system to record its state.

Messages are constantly in transit, and nodes are processing tasks asynchronously.

Taking a naive snapshot by simply querying each node’s state independently would result in an inconsistent view. For example, the snapshot might capture a message as received by one node, but not yet sent according to the sender's recorded state, creating the illusion of an impossible state.

The Chandy-Lamport algorithm provides a classic solution to this problem. It allows a system to capture a consistent global snapshot without stopping its normal operation. The core idea involves:

• Initiation: A process starts the snapshot by recording its own local state and sending a special marker message on all of its outgoing communication channels.

• First marker receipt: When a process receives a marker on an incoming channel for the first time, it records its own local state. It also marks that channel as empty, and no events are recorded on it as part of the snapshot. Then, it sends markers on all of its outgoing channels.

• Subsequent markers: After recording its state, the process must keep track of its other incoming channels (all the ones on which it hasn’t yet seen a marker). For each such channel, it records all the regular messages that arrive until the marker for that channel is received. Once the marker arrives, it stops recording messages on that channel. The collected messages represent the state of the channel at the time the snapshot was taken.

• Termination: The snapshot is complete once every process has recorded its local state and has received a marker on each of its incoming channels.

The resulting snapshot is guaranteed to be globally consistent, making this technique fundamental for building reliable distributed systems that can recover from failures or be analyzed for correctness. The slides below illustrate how the Chandy-Lamport algorithm captures a distributed snapshot in a system with three processes: P0, P1, and P2.

Let’s now test your understanding of the concept of time in distributed systems with a quick question.

If you’re not sure how to do this, click the “Want to know the correct answer?” button.

Conclusion

Understanding logical time, event ordering, and consistent state is a practical necessity for building robust, scalable, and correct distributed systems.

The concepts introduced by Lamport and the vector clock algorithms form the foundation of numerous modern technologies, including cloud databases and large-scale data processing frameworks. As you continue your System Design journey, you will see these principles appear repeatedly, especially when we discuss data consistency and fault tolerance.