--- title: "State recording, debugging, distributed cuts" subject: "Distributed System" chapter: 5 key: "semester_7/distributed_system:state-recording-cut" source: https://www.bctengineer.com/q/semester_7/distributed_system/state-recording-cut site: BCT Engineering --- # State recording, debugging, distributed cuts Distributed System · Chapter 5: Time and State in Distributed Systems - Asked in: 2073 Shrawan, 4+6 marks - Video: [Global state in Distributed Systems, Consistent and Inconsistent cuts](https://www.youtube.com/watch?v=wiBWIdV8Eec) — Simplified Computer Science Concepts-Prof. Rutuja - Page: https://www.bctengineer.com/q/semester_7/distributed_system/state-recording-cut - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5 ## Question What are the principle applications of state recording and distributed debugging? Determine the types of distributed CUT in the following figure. [Figure: three process time-lines P0, P1, P2 drawn horizontally, with diagonal message arrows passing between the processes (P0 to P1, P1 to P2, P2 to P0 and P1 to P0 etc.) and four dashed cut lines C1, C2, C3 and C4 drawn across the three time-lines from left to right; exact message endpoints are not legible in the scan.] ## Short answer State recording is used for deadlock detection, termination detection, checkpointing, and garbage collection. Distributed debugging checks safety and liveness predicates. In the figure, C1 is consistent, C2 is inconsistent (message crosses from right to left), C3 is consistent with in-transit messages, and C4 is strongly consistent. ## Answer #### Applications of global state recording 1. **Garbage collection**: find objects with no references anywhere in the system, including references in messages in transit. 2. **Deadlock detection**: build a wait-for graph from a consistent state to see a cycle. 3. **Termination detection**: check that all processes are passive and no messages are in transit. 4. **Checkpointing and recovery**: save a consistent state to restart after a failure. 5. **Detecting stable properties** such as lost tokens, and measuring system load. #### Applications of distributed debugging 1. Check **predicates** (global conditions) during an execution, for example "lock is held by two processes" (safety) or "the system is deadlocked". 2. Detect that a **safety bug** (bad state, such as violation of mutual exclusion) occurred, or that a **liveness** condition never occurs. 3. Replay and trace executions, find causal relations of events, and locate faults. 4. Monitor consistency of replicated data and correct ordering of messages. Debugging uses consistent cuts and vector clocks to evaluate predicates on states which may have happened. #### Types of distributed cuts A **cut** is a set of events, a prefix of each process's history; its frontier is the last event of each process in the cut. - **Consistent cut**: for every event in the cut, all events that happened before it are also in the cut. Equivalently, no message crosses the cut line from the future to the past (no message received inside the cut whose send is outside). - **Inconsistent cut**: contains a receive event whose send event lies outside the cut (message travels backward across the cut line, from right to left in the figure). - A consistent cut may have messages in transit (sent inside, received outside), which form the channel state. - **Strongly consistent cut**: consistent and with no messages in transit at all. #### Classifying C1 to C4 The message endpoints are not legible, so the usual method is applied under the following assumption: a cut that is a vertical-like line leaning forward in time from top to bottom in the same direction as messages is consistent; one that is crossed by a message arrow going from its right side to its left side is inconsistent. | Cut | Check | Type | |---|---|---| | C1 | no message arrow enters the cut from the right | consistent | | C2 | some message crosses from right to left (receive in cut, send outside) | inconsistent | | C3 | messages only cross left to right | consistent, with messages in transit | | C4 | no message crosses at all | strongly consistent | For each cut, trace every arrow that crosses it: send before the line and receive after the line is allowed; the reverse makes the cut inconsistent. Consistent cuts correspond to valid global states that the system could have passed through. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which is an application of global state recording? A. Compiling IDL B. Increasing CPU speed C. Clock drift measurement D. Deadlock detection using a wait-for graph Answer: D. A consistent state lets you detect cycles and other stable properties. (Key point: Applications of state recording) 2. When is a cut consistent? A. For every event in the cut, all events that happened before it are also in the cut B. It contains no events C. It contains a receive without its send D. It crosses no process Answer: A. No message may be received inside the cut with its send outside. (Key point: Consistent cut) 3. What makes a cut inconsistent? A. A message is in transit B. A receive event is in the cut whose send lies outside C. A send is in the cut and its receive outside D. It has events from three processes Answer: B. The message travels backward across the cut, impossible in real execution. (Key point: Inconsistent cut) 4. What is a strongly consistent cut? A. A cut with all messages in transit B. A cut with only one process C. A consistent cut with no messages in transit D. An inconsistent cut Answer: C. There is no channel state at all. (Key point: Strongly consistent) ## Related in Distributed System - [Short note: Distributed debugging](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-debugging-note) — Distributed System, chapter 5 - [Short note: Distributed cut](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-cut-note) — Distributed System, chapter 5 - [Threads, checkpoint, distributed commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Athreads-checkpoint-commit) — Distributed System, chapter 3 - [Applications, advantages of DS](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ads-applications-advantages) — Distributed System, chapter 1 - [Homogeneous vs heterogeneous applications](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Ahomo-hetero-apps) — Distributed System, chapter 4 - [Short note: Process resilience](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aprocess-resilience-note) — Distributed System, chapter 9, asked 4× ## Related in other subjects - [Liang-Barsky: P1(-5,3), P2(15,9)](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Aliang-barsky-0-0-10-10) — Computer Graphics, chapter 3 - [Get data from P0, send to P1 (asm and C)](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3A8051-p0-to-p1-assembly-c) — Embedded System, chapter 9 - [Process to determine wire size](https://www.bctengineer.com/question.md?key=semester_1%2Fbasic_electrical_and_electronics_engineering%3Awire-size-determination) — Basic Electrical and Electronics Engineering, chapter 4 - [Short note: Total station principle, data recording](https://www.bctengineer.com/question.md?key=semester_4%2Fsurveying_ii%3Atotal-station-principle-data-recording) — Surveying II, chapter 9