#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"
}