Name
Abstract | ||
|---|---|---|
Global predicate detection is a fundamental problem in distributed systems and finds applications in many domains such as testing and debugging distributed programs. This paper presents an efficient distributed algorithm to detect conjunctive form global predicates in distributed systems. The algorithm detects the first consistent global state that satisfies the predicate even if the predicate is unstable. Unlike previously proposed run-time predicate detection algorithms, our algorithm does not require exchange of control messages during the normal computation. All the necessary information to detect predicates is piggybacked on computation messages of application programs. The algorithm is distributed because the predicate detection efforts as well as the necessary information are equally distributed among the processes. We prove the correctness of the algorithm and compare its performance with respect to message, storage, and computational complexities with that of the previously proposed run-time predicate detection algorithms. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/32.707701 | IEEE Trans. Software Eng. |
Keywords | Field | DocType |
predicate detection effort,normal computation,consistent global state,computation message,global predicate,run-time predicate detection algorithm,necessary information,local predicates,computational complexity,application program,global predicate detection,system testing,debugging,distributed algorithm,algorithm correctness,distributed system,computer applications,lattices,application software,software engineering,distributed algorithms,distributed systems,satisfiability,distributed computing | Computer science,Correctness,Theoretical computer science,Distributed algorithm,Predicate (grammar),Program testing,Software development,Computational complexity theory,Debugging,Computation | Journal |
Volume | Issue | ISSN |
24 | 8 | 0098-5589 |
Citations | PageRank | References |
29 | 1.28 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michel Hurfin | 1 | 266 | 29.30 |
| Masaaki Mizuno | 2 | 338 | 34.49 |
| Mukesh Singhal | 3 | 2602 | 259.07 |
| Michel Raynal | 4 | 4078 | 349.46 |