Submitted by:

The detection of global predicates is one of the fundamental problems in distributed computing. The difficulty of the problem arises due to the fact that there is no shared memory and no shared clock in a distributed system. Hence, no process has access to the global state. Therefore, the truth value of a global predicate cannot be determined by a single process. Determining the truth value of a global predicate requires the participation of those processes which can change the value of the global predicate. The importance of global predicate detection can be seen in several domains such as designing, testing, and debugging of distributed programs. For example, predicate detection is crucial for implementing breakpoints in a distributed debugger. If we want to stop the debugger when local predicates on different processes become true, it is necessary to detect that all the local predicates on different processes became true concurrently. This is not an easy task given that no process has access to the global state of the distributed system. In fact Chase and Garg have shown that global predicate detection problem is NP-complete [2]. In this paper, our objective is to present several algorithms used to detect globa