TOWARDS THE CONSTRUCTION OF DISTRIBUTED DETECTION PROGRAMS, WITH AN APPLICATION TO DISTRIBUTED TERMINATION

Methodological design of distributed programs is necessary if one is t o master the complexity of parallelism. The class of control programs, whose purpose is to observe or detect properties of an underlying pro gram, plays an important role in distributed computing. The detection of a property generally rests upon consistent evaluations of a predica te; such a predicate can be global, i.e. involve states of several pro cesses and channels of the observed program. Unfortunately, in a distr ibuted system, the consistency of an evaluation cannot be trivially ob tained. This is a central problem in distributed evaluations. This pap er addresses the problem of distributed evaluation, used as a basic to ol for solution of general distributed detection problems. A new evalu ation paradigm is put forward, and a general distributed detection pro gram is designed, introducing the iterative scheme of guarded waves se quence. The case of distributed termination detection is then taken to illustrate the proposed methodological design.