#Number
TR-PDS-1997-006

#Title
Predicate Control in Distributed Systems

#Author
Ashis Tarafdar
Vijay K. Garg

#Abstract
A number of important problems in asynchronous distributed systems
involve controlling a distributed system to maintain 
invariant global properties. Usually, the complexity of 
synchronization to maintain these invariants is part of distributed
algorithm design. We propose an alternative approach in which
the invariant may be specified to a supervisory control system.
The control system then bears the burden of synchronizing the distributed 
system in order to maintain the invariant. The {\em predicate
control problem\/} involves transforming a general global 
invariant into a synchronization strategy for a control system.

We formalize the predicate control problem in both off-line
and on-line scenarios. We motivate its relevance with real-world
examples. We prove that general off-line predicate control is
NP-hard. However, we provide an efficient solution for off-line
predicate control for the class of disjunctive predicates. We further 
solve on-line predicate control for disjunctive predicates under 
certain restrictions. 



#Bib
@TechReport{,
  author =   "Ashis Tarafdar and Vijay K. Garg",
  title =    "Predicate Control in Distributed Systems",
  institution =  "Parallel and Distributed Systems Laboratory, ECE
                  Dept. University of Texas at Austin",
  year =         "1997",
  number =    "ECE-PDS-1997-006",
  note =     "available via ftp or WWW at maple.ece.utexas.edu
          as technical report TR-PDS-1997-006"
}