Thumbnail
Access Restriction
Open

Author Roger, J. ♦ Kilgore, Mitchell Richard ♦ Garg, Vijay ♦ Garg, Vijay K. ♦ Chase, Craig ♦ Mitchell, J. Roger ♦ Kilgore, Richard
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Main Application ♦ Distributed System ♦ Conjunctive Channel ♦ Previous Work ♦ Local Predicate ♦ Efficient Algorithm ♦ Special Case ♦ Message Complexity ♦ Distributed Program ♦ Global Predicate ♦ Global Virtual Time ♦ Efficient Detection ♦ Channel Predicate ♦ Many Problem ♦ Distributed Programming Environment ♦ Many Property ♦ Boolean Formula
Description This paper discusses efficient detection of global predicates in a distributed program. 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 efficient detection of global predicates. We show that 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. The main application of our results are in debugging and testing of distributed programs. Our algorithms have been ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1995-01-01
Publisher Institution In Proc. of the International Conference on System Sciences