Ordering errors in distributed programs (communication, debug, operating system, language)
Aaron J. Gordon · 1985
With processors becoming small and inexpensive, many researchers attempt to decrease program runtime by combining processors into a multicomputer and running programs distributed over these processors. Debugging in a distributed environment is different from debugging on a uniprocessor. On a uniprocessor, the order in which a process's events occur is deterministic. 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. Traditional methods of debugging (such as putting in print statements and recompiling the program or recompiling the program with a debug flag on) are inadequate since they change the program and therefore change the timing. For this research, I have investigated distributed program bugs that depend on the relative order between events. These ordering errors include events which always occur in the wrong order and events whose order of occurrence is time-dependent. In this research, I characterize these timing errors and misorderings and show necessary conditions for their occurrence. Using my model of a distributed system, I prove which features can be used in combination to avoid ordering errors. I use these results to make suggestions to those writing distributed programs, developing distributed programming languages and designing distributed operating systems. I then explain drawbacks to preventing ordering errors and show ways to detect them as they occur. Finally, I describe a tool (called TAP) to aid the programmer in discovering the causes of ordering errors in running programs. I also show that TAP is useful in finding other types of distributed program bugs.