#Number
TR-PDS-1995-004
#Title
On Techniques and their Limitations for the Global Predicate Detection
Problem in Distributed Systems
#Author
Craig M. Chase and Vijay K. Garg
#Abstract
We show that the problem of predicate detection in distributed
systems is NP-complete. We introduce a class of predicates,
linear predicates, such that for any linear predicate B there
exists an efficient detection of the least cut satisfying B. We
show that the least cut may not even exist if the predicate is not
linear. The dual of linearity is post-linearity. These
properties generalize several known properties of distributed
systems, such as the set of consistent 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
distributed 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
problem. We give a simple transformation of the traditional poset
representation of a distributed execution into a flow graph.
We show that computing the max-flow of this graph is equivalent to
identifying a consistent cut which minimizes the sum of a set of
distributed variables. This result solves a previously open problem
in predicate detection, establishing the existance of an efficient
algorithm to detect predicates of the form x1 + x2 ... + xN < C
where the xi are variables on different processes, C is some
constant, and N is larger than 2.
#Bib
@TechReport{CG95,
author = "Craig M. Chase and Vijay K. Garg",
title = "On Techniques and their Limitations for the Global
Predicate Detection Problem in Distributed Systems",
institution = "Parallel and Distributed Systems Laboratory, ECE
Dept. University of Texas at Austin",
year = "1995",
number = "TR-PDS-1995-004",
note = "submitted to the 1995 conference on Principles of
Distributed Computing",
note = "available via ftp or WWW at maple.ece.utexas.edu
as technical report TR-PDS-1995-004",
}