Handling Timing Errors in Distributed Programs

In a distributed environment, events occur concurrently on different processors. The order in which events occur cannot be easily determined; a program that works correctly one time may fail subsequently if the timing between processors changes. For this research, we have investigated distributed program bugs that depend on the relative order between events. We describe a tool (called TAP) to aid the programmer in discovering the causes of timing errors in running programs. TAP, a tool similar to a postmortem debugger, uses the history of interprocess communication to construct a timing graph, a directed graph where an edge joins node x to node y if event x directly precedes event y in time. The programmer can then use TAP to look at the graph to find the events that occurred in an unacceptable order. Because of the nondeterministic nature of distributed programs, we feel a history-keeping mechanism must always be active so that bugs can be dealt with as they occur. Our goal is to collect enough information at run time to construct the timing graph if needed. Since it is always active, this mechanism must be efficient. We also describe experiments run using TAP and report the impact that TAP'S history-keeping mechanism has on the running time of various distributed programs.