Skip to main content

State recording, debugging, distributed cuts

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.

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.]

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.

CutCheckType
C1no message arrow enters the cut from the rightconsistent
C2some message crosses from right to left (receive in cut, send outside)inconsistent
C3messages only cross left to rightconsistent, with messages in transit
C4no message crosses at allstrongly 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.

Related questions

All Distributed System chapter 5 questions →