Algoritmos Distribuídos para Detecção de Predicados Globais

• L. M. A. Drummond UFF
• V. C. Barbosa UFRJ

DOI: https://doi.org/10.5753/sbac-pad.1995.19872

Resumo

Um dos aspectos mais importantes de depuradores de programas paralelos distribuídos consiste na facilidade de se estabelecerem breakpoints que possam ser descritos por predicados envolvendo estados globais e, então, denominados predicados globais. Neste artigo consideramos o projeto de algoritmos distribuídos para a detecção de tais breakpoints em programas paralelos distribuídos e fornecemos quatro algoritmos, um para cada tipo diferente de breakpoint. Um dos algoritmos detecta a ocorrência de breakpoints incondicionais, enquanto os outros três detectam a ocorrência de breakpoints sobre predicados disjuntivos, predicados conjuntivos estáveis e predicados conjuntivos genéricos. Todos os algoritmos apresentados detectam os breakpoints nos estados globais mais adiantados em relação às propriedades envolvidas. No caso de breakpoint incondicional, tal estado global mais adiantado deve coincidir exatamente com os breakpoints incondiconais locais requisitados para os processos que realmente participam do breakpoint. No caso dos outros breakpoints (condicionais), detecta-se o estado global mais adiantado onde o predicado disjuntivo ou o conjuntivo considerado é verdadeiro.

Referências

Chandy, K. M., and Lamport, L. Distributed snapshots: determining global states of distributed systems. ACM Trans. on Computer Systems 3 (1985), 63-75.

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.