Algoritmos Distribuídos para Detecção de Predicados Globais
Abstract
The ability to set breakpoints, that can be expressed by predicates involving global states and thus called global predicates, stands as one of the most important issues in the debugging of message-passing programs. We consider in this paper the design of fully distributed algorithms for the detection of such breakpoints in distributed parallel programs, and provide four algorithms, each for a different type of breakpoint. One of the algorithms detects the occurrence of unconditional breakpoints, while the other three detect the occurrence of breakpoints on disjunctive predicates, stable conjunctive predicates and generic conjunctive predicates. All the algorithms we present detect breakpoints in the form of earliest global states with respect to the particular property involved. In the case of unconditional breakpoint, such an earliest global state must coincide exactly with the requested local unconditional breakpoints for the processes that do actually participate in the breakpoint. In the case of the other (conditional) breakpoints, what is detected is the earliest global s tate at which either the disjunctive or conjunctive predicate under consideration is true.
References
Cooper, R., and Marzullo, K. Consistent detection of global predicates. Proc. of the ACM Workshop on Parallel and Distributed Debugging, 1991, pp. 167-174.
Drummond, L. A., and Barbosa, V. C. Distributed Breakpoint Detection in Message-Passing Programs. Publicações técnicas COPPE-UFRJ, ES-306/94, submetido para publicação.
Garg, V. K., and Waldecker, B. Detection of unstable predicates in distributed programs. Proc. of the Twelfth Conference on Foundations of Software Technology & Theoretical Computer Science, 1992, pp. 253-264.
Goldberg, A. P., Gopal, A., Lowry, A., and Strom, R. Restoring consistent global states of distributed computations. Proc. of the ACM Workshop on Parallel and Distributed Debugging, 1991, pp. 144-154.
Haban, D., and Weigel, W. Global events and global breakpoints in distributed systems. Proc. of the Twenty-First International Conference on System Sciences, Vol. 2, 1988, pp. 166-175.
Lamport, L. Time, clocks, and the ordering of events in a distributed system. Comm. of the ACM 21 (1978), 558-565.
Manabe, Y., and Imase, M. Global conditions in debugging distributed programs. J. of Parallel and Distributed Computing 15 (1992), 62-69.
McDowell, C., and Helmbold, D. Debugging concurrent programs. ACM Computing Surveys 21 (1989), 593-622.
Miller, B., and Choi, J. Breakpoints and halting in distributed programs. Proc. of the Eighth International Conference on Distributed Computing Systems, 1988, pp. 316-323.
Spezialetti, M. An approach to reducing delays in recognizing distributed event occurrences. In Proc. of the ACM Workshop on Parallel and Distributed Debugging, 1991, pp. 155-166.
Spezialetti, M., and Keams,.J. P. Simultaneous regions: a framework for the consistent monitoring of distributed systems. Proc. of the Ninth International Conference on Distributed Computing Systems, 1989, pp. 61-68.
Tomlinson, A. I., and Garg, V. K. Detecting relational global predicates in distributed systems. Proc. of the ACM/ONR Workshop on Parallel and Distributed Debugging, 1993, pp. 21 - 31.
