#Number
TR-PDS-2003-005

#Title
Predicate Control: Synchronization in Distributed Computations with Look-ahead

#Author
Ashis Tarafdar
Vijay K. Garg

#Abstract 

The predicate control problem involves synchronizing a distributed
computation to maintain a given global predicate. In contrast with many
popular distributed synchronization problems such as mutual exclusion,
readers writers, and dining philosophers, predicate control assumes a
look-ahead, so that the computation is an off-line rather
than an on-line input. Predicate control is targeted towards applications
such as rollback recovery, debugging, and optimistic computing, in which
such computation look-ahead is natural.

We define predicate control formally and show that, in its full
generality, the problem is NP-Complete. We find efficient solutions for
some important classes of predicates including ``disjunctive predicates'',
``mutual exclusion predicates'', and ``readers writers predicates''.  For each
class of predicates, we determine the necessary and sufficient conditions
for solving predicate control and describe an efficient algorithm for
determining a synchronization strategy. In the case of ``independent
mutual exclusion predicates'', we determine that predicate control is
NP-Complete and describe an efficient algorithm that finds a solution under
certain constraints.

	
#Bib
@techreport{TR-PDS-2003-005,
  author = 	 "Ashis Tarafdar and Vijay K. Garg",
  title = 	 "Predicate Control: Synchronization in Distributed Computations
                  with Look-ahead",
  instituition = "The University of Texas at Austin",
  year = 	 "2003",
  number =	 "TR-PDS-2003-005",
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-2003-005"
}