Clock sync problems; Chandy-Lamport

Common problems of physical clock synchronization algorithms

1. Clock drift and skew: oscillators run at different speeds, so clocks diverge between synchronisations.
2. Unpredictable message delay: the accuracy is limited by the variable network delay and its asymmetry (Cristian, NTP).
3. Single point of failure: a single time server (Cristian) fails or gives wrong time; a faulty master affects all (Berkeley).
4. Faulty or malicious clocks: wrong values corrupt the average (need outlier rejection).
5. Clock cannot move backwards: adjusting must be gradual, which takes time.
6. Scalability and traffic: frequent polling loads the network.
7. Accuracy limited to milliseconds; needs UTC reference for external sync.

Chandy-Lamport global snapshot algorithm

Purpose: record a consistent global state (state of every process and of every channel) of a distributed system without stopping it. Assumptions: channels are FIFO and reliable; the processes are connected; any process can start the snapshot.

Marker rule for sending: After a process Pi records its state, it sends a marker on each outgoing channel before sending any further messages.

Marker receiving rule: On receipt of a marker on incoming channel c:

• If Pi has not yet recorded its state: it records its own state, records the state of channel c as empty, and starts recording messages arriving on its other incoming channels (and sends markers on all outgoing channels).
• Else (already recorded): the state of channel c is the sequence of messages received on c after Pi recorded its state and before the marker arrived.

Initiation: Any process records its state and sends markers on all outgoing channels.

Termination: The snapshot is done when every process has received a marker on each of its incoming channels. The recorded process states and channel states are then collected at one place.

 P1 --m--> P2        P1 records state S1, sends marker
 P1 --marker--> P2   P2 gets marker first time:
                       records S2, channel(P1->P2) = {}
                       sends markers on its outputs
 Messages arriving at P2 on other channels before their
 markers are saved as that channel's state.

The recorded global state is consistent (a consistent cut): no message is recorded as received without being recorded as sent. It is used for deadlock detection, termination detection and checkpointing.