An Algorithm for Finding the Causal Distributed Breakpoint

Acausal distributed breakpointis one of the fundamental mechanisms for debugging distributed programs. It is initiated by a sequential breakpoint in one process of a distributed computation, and restores each process to theearlieststate that reflects all events that happened causally before the sequential breakpoint. This paper presents an algorithm for finding the causal distributed breakpoint when a sequential breakpoint occurs. To find the causal distributed breakpoint efficiently, some information about dependency of events is piggybacked in every message and is logged at each process. The algorithm requiresO(1) information in each message and finds the causal distributed breakpoint inO(nlogn+m) time, wherendenotes the number of processes andmdenotes the number of distinct pairs of processes directly communicating with each other.