\section{Predicate Detection}

Predicate detection involves determining whether a global condition
(predicate) occurs while running a concurrent program.  Predicate
detection is a widely-studied problem \cite{bm93, vg96}.  Approaches to
solving predicate detection are divided into three categories: global
snapshot based \cite{cl85}, lattice construction based \cite{cm91}, and
predicate restriction based \cite{gw94} approaches. The first approach
can detect only {\em stable\/} predicates (which remain true once they
become true), and the second approach uses the interleaving model of
concurrency and, therefore, suffers from combinatorial explosion. The
last approach uses the partial order model and limits itself to classes
of predicates which can be detected efficiently. 


\subsection{Past Work: Conjunctive Predicate Detection in the Potential
Causality Model}

Predicate detection has used happened before as its model of a
concurrent computation. In a previous work \cite{tg98-icdcs}, we
motivated the use of the potential causality model in predicate
detection and presented results in solving predicate detection in the
potential causality model. We followed the third of the above mentioned
approaches that limits itself to classes of predicates which can be
detected efficiently. 

We focused on the important class of {\em conjunctive predicates\/},
which express a conjunction of local predicates (or, in other words,
the combined occurrence of local conditions).  The problem of detecting
such predicates efficiently was previously solved for the happened
before model in \cite{gw94}. We demonstrated that for the potential
causality model, this problem is NP-complete. However, for certain
restricted, but useful, classes of computations, we designed efficient
algorithms to solve the problem. These classes of computations are {\em
send-ordered\/} computations or {\em receive-ordered\/} computations.
Receive-ordered (send-ordered) computations are those in which the
receive (send) events are totally ordered while the remaining events
may be partially ordered. An example of a receive-ordered computation
is one that arises often in client-server systems:  
\begin{verbatim}
   repeat
      receive a request ; 
      create a thread to process it 
   until done
\end{verbatim} 
Furthermore, although conjunctive predicate detection is NP-complete
for general computations, we demonstrated how to achieve an exponential
reduction over the naive approach.

We now discuss applications of conjunctive predicates in two application
areas: distributed debugging and, of course, our fault avoidance system.

\subsubsection*{Application 1: Distributed Debugging}
Just as breakpoints are useful in sequential debugging, {\em global
breakpoints\/} are useful in distributed debugging. It might
be required to halt execution if the computation ever enters 
a specified set of functions concurrently. For simplicity, suppose
there are two processes, and $f_1$ is a function in one process
and $f_2$ is a function in the other. Then, a specification of
a global breakpoint would be: 
$$ entered:f_1\ \wedge\ entered:f_2 $$


\subsubsection*{Application 2: Fault Avoidance}

Conjunctive predicates allow us to specify a broad class of 
synchronization faults. For example, if two segments of code
access the same data object concurrently, we have a race condition.
This could be detected by detecting the following conjunctive
predicate:
$$ P_1\ is\  writing\ object\ x\ \wedge\ P_2\ is\ reading\ object\ x $$

Another common synchronization fault is the notorious deadlock condition.
This can be specified as the following conjunctive predicate:
$$ P_1\ is\ waiting\ \wedge\ P_2\ is\ waiting\ \wedge\ \cdots\ P_n\ is\ waiting$$

\subsection{Proposed Work: Synchronization Fault Detection in the
Potential Causality Model}

Our focus will be on detecting synchronization faults, such as race
conditions and deadlocks. We have shown how these may be specified as
conjunctive predicates, for which we have studied and solved the
predicate detection problem. Each of these has also been extensively
studied as special cases to give specialized solutions (in the happened
before model). We propose to study extending such solutions to the
potential causality model. 

%INC: Race detection, deadlock detection references

Although races and deadlocks are among the most common synchronization
faults, there are many other types of synchronization faults. We
propose to identify other useful synchronization faults and study the
corresponding predicate detection problems, especially in the potential
causality model.

