2.1 Clock Skew and Drift

In distributed systems, maintaining a consistent understanding of time is inherently challenging due to two key phenomena:

• Clock Skew: This refers to the difference in clock readings across processes. Imagine two servers managing bank transactions. If one server's clock is ahead by a few seconds, it might process a withdrawal request before a deposit, even though the deposit occurred first. This could lead to an incorrect insufficient balance error.
• Clock Drift: This arises when the clocks of different processes run at slightly different speeds, causing the skew to increase over time. For instance, if one server's clock is faster by 1 millisecond per second, over an hour, it will be 3.6 seconds ahead. Such discrepancies can accumulate and disrupt the system’s coherence.

2.2 Maximum Drift Rate (MDR)

To manage these challenges, we use the concept of Maximum Drift Rate (MDR), which quantifies how fast clocks can drift apart. This helps determine how often synchronization is required. For example:

$$t_{sync} = \frac{M}{2 \times MDR}$$

Here, $M$ represents the maximum allowable skew for the system. Consider a distributed video streaming service like Netflix, where synchronized timestamps ensure seamless playback across devices. If the MDR is known to be 1 microsecond per second and the system tolerates up to 1 millisecond skew, synchronization must occur at least every:

$$t_{sync} = \frac{0.001}{2 \times 0.000001} = 500 \text{ seconds (or ~8 minutes).}$$

By scheduling synchronization at this interval, the system prevents errors caused by skew or drift, ensuring consistency and fairness in operations.

3.1 External Synchronization

External synchronization ensures that processes align their clocks with an external reference, typically UTC. Two key algorithms are:

3.1.1 Cristian's Algorithm

Cristian's Algorithm helps a process synchronize its clock with an external time server by estimating the offset caused by message delays. The steps are:

• Step 1: Request Time: A process sends a "What is the time?" request to the time server and records the request's send time $t_0$ using its local clock.
• Step 2: Receive Reply: The server responds with the current time $t_s$ according to its clock. The process receives the reply at time $t_1$ (local clock).
• Step 3: Adjust Clock: The process calculates the adjusted time as: $$t_{adjusted} = t_s + \frac{t_1 - t_0}{2}$$ Here, $\frac{t_1 - t_0}{2}$ approximates the one-way network delay.

Practical Example: In online gaming, Cristian's Algorithm can synchronize players' devices to ensure events like firing or jumping are consistent. While simple, its accuracy is affected by variable network latency, making it suitable for scenarios where bounded but small errors are acceptable.

3.1.2 Network Time Protocol (NTP)

NTP synchronizes clocks hierarchically, minimizing error by considering asymmetric delays and network hierarchies. It operates as follows:

• Step 1: Multilevel Hierarchy: Servers are organized in a tree. Primary servers at the root synchronize directly with atomic clocks or GPS. Secondary servers synchronize with primary servers, and tertiary servers synchronize with secondary servers. Clients synchronize with their immediate parent node.
• Step 2: Exchange Messages: A client exchanges four timestamps with its parent:
  • Request send time: $t_1$ (client's clock).
  • Request receive time: $t_2$ (server's clock).
  • Response send time: $t_3$ (server's clock).
  • Response receive time: $t_4$ (client's clock).
• Step 3: Compute Offset: The client calculates its clock offset as: $$o = \frac{(t_2 - t_1) + (t_3 - t_4)}{2}$$
• Step 4: Adjust Clock: The client adjusts its clock by the calculated offset.

Practical Example: Email systems use NTP to ensure timestamp accuracy across global servers. For instance, an email sent from New York and received in Tokyo appears with consistent timestamps, enhancing reliability and user trust.

3.2 Internal Synchronization

Internal synchronization focuses on aligning clocks within a distributed group without external references. A widely used algorithm is:

3.2.1 Berkeley Algorithm

Berkeley's Algorithm relies on averaging to synchronize clocks in distributed systems. The steps are:

• Step 1: Collect Times: A central master process polls all other processes for their clock values, noting the message round-trip time (RTT) for each.
• Step 2: Calculate Average: The master computes the average clock time across all processes, adjusting for RTT by halving it: $$t_{average} = \frac{\sum (t_{i} + RTT_{i}/2)}{N}$$ Where $t_{i}$ is the clock value of process $i$.
• Step 3: Send Adjustments: The master sends each process the amount to adjust its clock (positive or negative).

Practical Example: Distributed weather sensors monitoring temperature in a region use the Berkeley Algorithm to align their timestamps. This ensures the collected data is temporally consistent for further analysis.

4.1 Lamport Timestamps

Lamport timestamps establish a logical ordering of events in distributed systems by assigning each event an integer timestamp. The algorithm ensures causality, meaning that if one event influences another, the first event will always have a smaller timestamp.

How it works:

• Event Execution: Each process maintains a local integer clock. When a process executes an event (e.g., a computation or message send), it increments its local clock by 1.
• Message Exchange: When a process sends a message, it includes the current value of its clock in the message.
• Message Receipt: Upon receiving a message with timestamp $T_{msg}$, the receiving process updates its clock to: $$T_{recv} = \max(T_{local}, T_{msg}) + 1$$

This ensures that if an event $A$ causally precedes an event $B$, their timestamps will satisfy $T(A) < T(B)$.

Limitation: Lamport timestamps cannot distinguish concurrent events (i.e., events with no causal relationship).

Practical Example:

Consider a chat application where messages must be displayed in the order they were sent. Lamport timestamps ensure that if a user replies to a message, the reply will always appear after the original message, regardless of network delays.

4.2 Vector Timestamps

Vector timestamps extend Lamport's approach to distinguish causally related events from concurrent events. Each process maintains a vector of clocks, where each element tracks its knowledge of other processes' clocks.

How it works:

• Event Execution: When a process executes an event, it increments its own clock element in the vector.
• Message Exchange: A process includes its vector timestamp in any message it sends.
• Message Receipt: Upon receiving a message with vector timestamp $V_{msg}$, the receiving process updates its vector as follows:
  • Increment its own clock: $V[i] = V[i] + 1$
  • Update other elements: $V[j] = \max(V_{msg}[j], V_{local}[j])$ for $j \neq i$

This mechanism allows detecting concurrent events ($V_1 ||| V_2$) and causally related events ($V_1 < V_2$).

Practical Example:

In collaborative document editing, vector timestamps help maintain consistency. For example, if two users edit the same section concurrently, vector timestamps ensure both changes are tracked, and conflicts are resolved intelligently.

5.1 CAP Theorem

The CAP theorem, proposed by Eric Brewer, states that a distributed system can satisfy at most two of the following three properties simultaneously:

• Consistency: Ensures that all nodes return the latest written value for any data. For example, in a banking application, if one user transfers money, all subsequent queries across nodes must reflect the updated balance.
• Availability: Guarantees that every request receives a response, even if some nodes fail. For instance, an e-commerce website must always allow users to browse and place orders, even during server downtime.
• Partition Tolerance: Allows the system to continue functioning despite network partitions. For example, during a data center outage, a globally distributed database should still allow operations on unaffected nodes.

Real-World Trade-Off: Modern systems prioritize partition tolerance (essential due to the internet’s inherent unreliability) and balance between consistency and availability based on use case:

• Consistency over Availability: Financial systems prioritize consistency to avoid incorrect account balances.
• Availability over Consistency: Social media platforms prioritize availability to ensure posts and comments can be accessed at all times.

5.2 Models of Consistency

Distributed systems adopt various consistency models to balance user requirements and system constraints:

• Eventual Consistency: Over time, all replicas of a data item converge to the same value, provided no new updates occur. For example, DNS systems propagate updates to domain records globally, ensuring eventual alignment despite initial discrepancies.
• Causal Consistency: Preserves the causality between writes. If operation A causes operation B, any client reading B must see A. In collaborative editing tools, causal consistency ensures that changes made by one user appear in the correct order for others.
• Strong Consistency: Ensures all clients view the same data simultaneously. For example, in stock trading platforms, the same stock price must be displayed to all traders at any given moment to ensure fairness and accuracy.

Practical Design: Distributed systems often choose models based on their workload. For example:

• Systems like Cassandra and DynamoDB use eventual consistency to prioritize availability.
• Google Spanner employs strong consistency for mission-critical applications.
• Causal consistency is often used in real-time collaboration tools like Google Docs.

6.1 Airline Reservation Systems

In airline reservation systems, distributed servers manage seat availability across multiple locations. Without synchronized clocks or proper event ordering, inconsistencies can arise, such as double-booking the same seat. For example:

• Scenario: Two customers simultaneously book the last available seat on a flight. Server A processes Customer 1's request, while Server B processes Customer 2's request.
• Issue: Without synchronized timestamps, both servers might independently record the seat as available, leading to conflicting bookings.
• Solution: Synchronizing clocks using protocols like NTP or implementing logical timestamps ensures consistent event ordering. Server B would recognize that Customer 1's booking was processed first and correctly reject Customer 2's request.

This prevents errors, ensuring accurate seat allocation and enhancing customer trust.

6.2 Key-Value Stores

Key-value stores like Cassandra and Riak use event ordering to ensure data consistency across distributed replicas. These databases often operate in eventual consistency mode to maximize availability and performance.

• Scenario: A shopping cart service uses a distributed database to store cart items. A customer adds an item to their cart on Server X, while another operation removes an item on Server Y.
• Issue: Without proper event ordering, these updates might conflict, leading to inconsistent cart states.
• Solution: Logical or vector timestamps help track the causality of updates. For instance, Server Y identifies that the addition on Server X occurred earlier and merges the updates correctly.

By maintaining correct replication and convergence, key-value stores provide reliable and high-performance data services in large-scale distributed systems.