Efficient detection of restricted classes of global predicates

We show that the problem of predicate detection in distributed systems is NP-complete. We intro- duce a class of predicates, linear predicates, such that for any linear predicate there exists an efficient detection of the least cut satisfying . The dual of linearity is post-linearity. These properties generalize several known properties of distributed systems, such as the set of consi stent cuts forms a lattice, and the WCP and GCP predicate dectection results given in earlier work. We define a more general class of predicates,semi-linear predicates, for which efficient algorithms are known to detect whether a predicate has occurred during an execution of a distri buted program. However, these methods may not identify the least such cut. Any stable predicate is an example of a semi-linear predicate. In addition, we show that certain unstable predicates can also be semi -linear, such as mutual exclusion violation. Finally, we show application of max-flow to the predicate detection probl em. This result solves a previously open problem in predicate detection, establishing the existen ce of an efficient algorithm to detect predicates of the form where are variables on different processes, is some constant, and is larger than 2.