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