| Proceedings of the 28th Annual Hawaii International Conference on System Sciences- 1995 Detecting Conjunctive Channel Predicates in a Distributed Programming Environment (2008) | |||||||||||||
Abstract | |||||||||||||
| Previous work in efficient detection of global predi-cates was restricted to predicates that could be specified as a boolean formula of local predicates. Many prop-erties in distributed systems, however, use the state of channels. In this paper, we introduce the concept of a channel predicate and provide an efficient algorithm to detect any boolean formula of local and channel pred-icates. We define a property called monotonicity for channel predicates. Monotonicity is crucial for efi-cient detection of global predicates. Many problems studied earlier such as detection of termination and computation of global virtual time are special cases of the problem considered in this paper. The message complexity of our algorithm is bounded by the num-ber of messages used by the program. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||