--- title: "Clock sync problems; Chandy-Lamport" subject: "Distributed System" chapter: 5 key: "semester_7/distributed_system:physical-clock-problems-chandy-lamport" source: https://www.bctengineer.com/q/semester_7/distributed_system/physical-clock-problems-chandy-lamport site: BCT Engineering --- # Clock sync problems; Chandy-Lamport Distributed System · Chapter 5: Time and State in Distributed Systems - Asked in: 2071 Shrawan, 3+5 marks - Video: [DC 3. Chandy Lamport Snapshot Algorithm in Distributed Computing with Example](https://www.youtube.com/watch?v=moSWS1Gha2g) — Cracking Concepts by Kiran Mary Matthew - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/physical-clock-problems-chandy-lamport - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5 ## Question What are the common problems of physical clock synchronization algorithms? Write Chandy-Lamport's algorithm for recording global states in Distributed System. ## Short answer Common problems: clock drift, variable network delays, single point of failure, faulty clocks, and inability to move clocks backward. Chandy-Lamport algorithm: a process records its state, sends markers on all channels; on first marker, record state and set that channel empty; on later markers, record intervening messages as channel state. This yields a consistent global snapshot. ## Answer #### 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. ```text 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which is a common problem of physical clock synchronisation algorithms? A. Events cannot be ordered at all B. Logical clocks overflow C. Clocks never drift D. Unpredictable message delay limits accuracy Answer: D. Variable and asymmetric delay limits accuracy of Cristian and NTP. (Key point: Sync problems) 2. When a process first receives a marker on channel c, what does it do? A. Records its own state, records c as empty and sends markers on all outgoing channels B. Records channel c's messages and ignores its own state C. Stops all computation D. Ignores the marker Answer: A. The first marker triggers state recording and marker propagation; c is recorded empty. (Key point: Marker rule) 3. If a process has already recorded its state, how is channel c's state determined on receiving a marker? A. Always empty B. The messages received on c after recording its state and before the marker C. All messages ever received on c D. Messages sent on c before the marker Answer: B. These messages were in transit at the snapshot. (Key point: Channel state) 4. What does Chandy-Lamport assume about channels? A. They may lose messages B. They are unordered C. They are FIFO and reliable D. They are synchronous Answer: C. FIFO ensures messages before the marker are separated from those after. (Key point: FIFO assumption) ## Related in Distributed System - [Physical clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-algorithm) — Distributed System, chapter 5 - [Clock synchronization need; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aclock-sync-lamport-need) — Distributed System, chapter 5 - [Problems of Lamport's clock; vector clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-problems-vector-clock) — Distributed System, chapter 5, asked 2× - [Lamport's logical clock algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-clock) — Distributed System, chapter 5, asked 5× - [Physical vs logical clock; sync method](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-difficulty) — Distributed System, chapter 5, asked 2× - [Vector clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Avector-clock-algorithm) — Distributed System, chapter 5, asked 2× ## Related in other subjects - [Clock synchronization in DFS](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Aclock-synchronization-dfs) — Big Data Technologies, chapter 1 - [Common problems of existing foundations](https://www.bctengineer.com/question.md?key=semester_6%2Fbuilding_technology%3Aproblems-existing-foundation) — Building Technology, chapter 2, asked 2× - [Global structure of multimedia system](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Aglobal-structure-multimedia-system) — Multimedia System, chapter 1, asked 3×