Detecting causal relationships in distributed computations: In search of the holy grail

Summary The paper shows that characterizing the causal relationship between significant events is an important but non-trivial aspect for understanding the behavior of distributed programs. An introduction to the notion of causality and its relation to logical time is given; some fundamental results concerning the characterization of causality are presented. Recent work on the detection of causal relationships in distributed computations is surveyed. The issue of observing distributed computations in a causally consistent way and the basic problems of detecting global predicates are discussed. To illustrate the major difficulties, some typical monitoring and debugging approaches are assessed, and it is demonstrated how their feasibility is severely limited by the fundamental problem to master the complexity of causal relationships. Reinhard Schwarz received a diploma in computer science from the University of Kaiserslautern, Germany, in 1990. Since then, he is working as a research assistant at the computer science department. His research interests include debugging and monitoring of distributed systems, runtime support for object-oriented distributed programming, and distributed algorithms. Friedemann Mattern received the diploma in computer science from Bonn University, Germany, and the Ph.D. degree from the University of Kaiserslautern, Germany, in 1983 and 1989, respectively. Since 1991 he is a professor of computer science at the University of Saarland in Saarbrücken, Germany. His current research interests include programming of distributed systems, distributed applications, and distributed algorithms.The work presented in this paper was carried out as part of the PARAWAN project supported by the Bundesministerium für Forschung und Technologie (BMFT)