AN ALGORITHM FOR FINDING THE CAUSAL DISTRIBUTED BREAKPOINT

A causal distributed breakpoint is one of the fundamental mechanisms f or debugging distributed programs. It is initiated by a sequential bre akpoint in one process of a distributed computation, and restores each process to the earliest state that reflects all events that happened causally before the sequential breakpoint. This paper presents an algo rithm for finding the causal distributed breakpoint when a sequential breakpoint occurs, To find the causal distributed breakpoint efficient ly, some information about dependency of events is piggybacked in ever y message and is logged at each process. The algorithm requires O(1) i nformation in each message and finds the causal distributed breakpoint in O(n log n + m) time, where n denotes the number of processes and r n denotes the number of distinct pairs of processes directly communica ting with each other, (C) 1997 Academic Press.