V.K. Garg, Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX, USA
C. Chase, Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX, USA
J.R. Mitchell, Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX, USA
R. Kilgore, Dept. of Electr. & Comput. Eng., Texas Univ., Austin, TX, USA
Previous work in efficient detection of global predicates was restricted to predicates that could be specified as a Boolean formula of local predicates. Many properties 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 predicates. We define a property called 'monotonicity' for channel predicates. Monotonicity is crucial for the efficient 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 number of messages used by the program.
Index Terms:
communication complexity; programming environments; telecommunication channels; Boolean functions; distributed processing; programming theory; message passing; conjunctive channel predicates detection; distributed programming environment; efficient global predicate detection; Boolean formula; local predicates; monotonicity; termination detection; global virtual time computation; message complexity
Citation:
V.K. Garg, C. Chase, J.R. Mitchell, R. Kilgore, "Detecting conjunctive channel predicates in a distributed programming environment," hicss, pp.232, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb