Short note: Distributed debugging

Distributed debugging means finding errors in programs running on several machines, where there is no global clock and events happen concurrently, so a bug may depend on a particular interleaving of events.

Main ideas:

• Global state predicates: the debugger evaluates a condition on the global state, e.g. "two processes are in the critical section" (a safety fault), "the system is deadlocked" or "the lock token is lost".
• Consistent global states: the monitor collects local states with vector or Lamport timestamps from all processes and forms consistent cuts. It need not stop the system; Chandy-Lamport snapshots can be used.
• Possibly Φ: there is some consistent global state, on at least one possible ordering (linearisation) of the observed execution, in which predicate Φ is true. Definitely Φ: on every possible ordering of the observed execution, Φ is true in some consistent global state.
• Techniques: logging with timestamps, message tracing, replay of a recorded execution, and breakpoints with causal ordering.
• Difficulties: the probe effect (monitoring changes timing), non-determinism, large amounts of trace data, and the absence of a global clock.

Detecting stable predicates (once true, they stay true: deadlock, termination) is easy with a snapshot; unstable predicates need examination of the lattice of consistent states.