Clocks, ordering and mutual exclusion notes — Unit 2

In a centralized system, time is unambiguous. There is one CPU clock. In a distributed system, there is no global clock. Every node has its own quartz crystal clock, and they drift apart.

⇒1.1 Clock Drift

Because of temperature and manufacturing differences, no two clocks tick at the exact same rate. If Node A thinks it is 12:00:00 and Node B thinks it is 12:00:05, and a file is updated on both, determining which update came 'first' is impossible without synchronization.

Physical clocks attempt to keep the actual hardware clocks of machines in sync.

⇒2.1 UTC

Universal Coordinated Time (UTC) is the global standard, broadcast by satellites (GPS) and shortwave radio. Computers can sync to a time server connected to a UTC receiver.

However, due to network latency, when a time server tells a computer 'It is exactly 12:00:00', the packet takes time to arrive. By the time the computer receives it, it is actually 12:00:00 plus the network delay.

Cristian's algorithm is a method for synchronizing a client to a time server, accounting for network delay.

⇒3.1 The Process

• 1. Client requests time at `T_0`.
• 2. Server receives request and responds with its current time `T_server`.
• 3. Client receives response at `T_1`.

The client calculates the Round Trip Time (RTT) as `T_1 - T_0`. Assuming network delay is symmetric, the one-way delay is `RTT/2`.

The client sets its clock to: `T_server + (RTT / 2)`.

Unlike Cristian's, the Berkeley algorithm assumes no machine has an accurate UTC receiver. It aims to achieve internal synchronization (all machines agree on a time, even if it's not the real-world time).

⇒4.1 The Process

• 1. A master node polls all slave nodes for their current time.
• 2. The master calculates the average time of all responding nodes (including itself), ignoring outliers (faulty clocks).
• 3. Instead of sending the new time, the master tells each node how much to adjust its clock (e.g., 'Speed up by +15ms' or 'Slow down by -10ms').

NTP is the industry standard for synchronizing clocks over the Internet.

⇒5.1 The Stratum Architecture

NTP uses a hierarchical system.

• Stratum 0: High-precision atomic clocks or GPS receivers. They do not connect to the network.
• Stratum 1: Servers directly connected to Stratum 0 devices. The most accurate servers.
• Stratum 2: Servers that sync from Stratum 1 over the network.
• Stratum 3: Sync from Stratum 2, and so on.

NTP uses statistical algorithms to filter out variable network latency and can keep machines synced within milliseconds.

For many distributed algorithms (like resolving conflicts in a database), the exact physical time doesn't matter. What matters is the order of events. Did Event A happen before Event B?

⇒6.1 The 'Happens-Before' Relation

Defined by Leslie Lamport, the relation `a -> b` (a happens before b) holds if:

• 1. `a` and `b` are events in the same process, and `a` occurs before `b`.
• 2. `a` is the event of a message being sent by one process, and `b` is the event of the message being received by another.
• 3. Transitivity: If `a -> b` and `b -> c`, then `a -> c`.

If `a` does not happen before `b`, and `b` does not happen before `a`, they are concurrent.

Lamport proposed a software counter (a logical clock) to implement the 'happens-before' relation.

⇒7.1 The Rules

• 1. Each process `Pi` maintains a local counter `Ci`, initially 0.
• 2. Before executing an event, `Pi` increments `Ci = Ci + 1`.
• 3. When `Pi` sends a message `m`, it piggybacks its current timestamp `t = Ci` onto the message `(m, t)`.
• 4. When a process `Pj` receives a message `(m, t)`, it updates its own clock to be strictly greater than both its current time and the message's time: `Cj = max(Cj, t) + 1`.

Lamport timestamps have a flaw: if `C(a) < C(b)`, we cannot conclude that `a` happened before `b`. They might be concurrent. Vector clocks solve this.

⇒8.1 The Mechanism

Instead of a single integer, each process keeps an array (a vector) of clocks, one for every process in the system.

• Process `Pi` has vector `Vi`.
• When `Pi` does an event, it increments its own slot: `Vi[i] = Vi[i] + 1`.
• When sending a message, `Pi` attaches its entire vector `Vi`.
• When `Pj` receives it, it updates its own vector slot-by-slot: `Vj[k] = max(Vj[k], Vi[k])` for all `k`, and then increments its own slot `Vj[j]++`.

With vector clocks, if `V(a) < V(b)`, then `a` definitely happened before `b`.

In a single computer, accessing a shared resource (like a file) safely is done using mutexes or semaphores in RAM. In a distributed system, processes across different networks must coordinate to prevent data corruption.

⇒9.1 Requirements

A distributed mutual exclusion algorithm must ensure:

• Safety: Only one process can hold the lock (enter the critical section) at a time.
• Liveness: A process requesting entry will eventually be allowed in (no deadlock/starvation).
• Ordering: If A requests the lock before B, A should get it first.

The simplest approach.

⇒10.1 The Mechanism

One node is designated as the Coordinator. To access the shared resource, a process sends a 'REQUEST' message to the Coordinator. If no one has the lock, the Coordinator sends 'OK'. If the lock is held, the Coordinator queues the request.

When the process is done, it sends a 'RELEASE' message to the Coordinator, which then sends 'OK' to the next process in the queue.

Drawback: The Coordinator is a single point of failure and a performance bottleneck.

A completely decentralized approach based on Lamport timestamps.

⇒11.1 The Mechanism

When a process wants the lock, it sends a `REQUEST(resource, timestamp, process_id)` message to ALL other processes.

When a process receives a REQUEST:

• If it doesn't want the lock, it replies `OK`.
• If it currently holds the lock, it does not reply (queues the request).
• If it also wants the lock, it compares timestamps. The lowest timestamp wins. If the incoming timestamp is lower, it replies `OK`. If its own is lower, it queues the request.

A process enters the critical section ONLY when it receives an `OK` from ALL other processes. Very heavy on network traffic.

Nodes are logically organized in a ring (regardless of physical network topology).

⇒12.1 The Mechanism

A single 'Token' circulates continuously around the ring. When a process receives the token:

• If it needs the resource, it holds the token, enters the critical section, does the work, and then passes the token to the next node.
• If it does not need the resource, it simply passes the token to the next node immediately.

Advantage: Fair, no starvation. Disadvantage: If the token is lost (node crashes while holding it), the system halts. Generating a new token requires complex election algorithms.

Determining the overall 'state' of a distributed system is incredibly difficult because by the time you poll Node B, Node A might have changed its state.

⇒13.1 Chandy-Lamport Algorithm

Used to record a consistent global snapshot (e.g., for taking a distributed backup or detecting deadlocks).

It uses 'marker' messages. An initiator saves its local state and sends a marker out on all its outgoing channels. When a node receives a marker for the first time, it records its own state, and forwards the marker. It guarantees a snapshot that represents a state that could have existed.

• Physical Clocks: Difficult to sync perfectly. NTP uses hierarchical syncing to combat network latency.
• Logical Clocks: Lamport timestamps track the order of events. Vector clocks prove causality.
• Mutual Exclusion: Centralized is easy but fragile. Distributed (Ricart-Agrawala) is robust but heavy on network traffic. Token Ring is fair but vulnerable to token loss.
• Global State: Chandy-Lamport algorithm uses markers to capture a consistent system-wide snapshot.