Intractability results in predicate detection
It has been shown that global predicate detection in a distributed computation is an NP-complete problem in general. However, efficient predicate detection algorithms exist for some subclasses of predicates, such as stable predicates, observer-independent predicates, conjunctions of local predicates, channel predicates, etc. We show here that the problem of deciding whether a given predicate is a member of any of these tractable subclasses is NP-hard in general. We also explore the tractability of linear and regular predicates. In particular, we show that, unless RP = NP, there is no polynomial-time algorithm to detect possibly: B for linear and regular predicates B. (c) 2005 Elsevier B.V. All rights reserved.
predicate detection distributed computing computational complexity distributed debugging