\section{Modeling Concurrent Computations}

Many applications, such as mutual exclusion and deterministic replay,
need to know the order in which events happen in time. In a distributed
system, events on different processes do not share a common clock. This
makes it impossible to determine their order in real time using
time-stamping mechanisms. Lamport \cite{ll78} introduced logical time
to order distributed events in a manner that approximates their real
time order.  To model logical time, Lamport defined the {\em happened
before\/} relation, denoted by $\hb$. An event happened before another
event if it precedes it in logical time. Two events incomparable by the
happened before relation are said to be {\em concurrent\/}, denoted by
$\|$.

If an event happens before another event, it has the potential for
causing that event. Many applications, such as recovery and debugging,
require the tracking of such causal dependencies. Mattern \cite{fm89}
realized that such applications would benefit by a mechanism to quickly
determine the happened before relation between events.  Mattern,
therefore, proposed a vector clock mechanism that allows the happened
before relation between events to be deduced.

An event that happens before another event need not necessarily cause
it. This is implicit when we say that happened before tracks {\em
potential\/} causality. Therefore, an inherent problem in using
happened before in applications that require causality tracking is that
sometimes events that are independent are believed to have a causal
dependency.  This phenomenon is called {\em false causality\/}. While
any approximation of causality must have false causality, the happened
before model was found to fall particularly short in this respect
\cite{cs93, sb97, tg98-icdcs}.

\subsection{Past Work: The Potential Causality Model}

\begin{figure}
\centerline{\epsfbox{Figures/spectrum.eps}}
\caption{Spectrum of models \label{spectrum-fig}}
\end{figure}

In a recent work \cite{tg98-tr}, we emphasized the distinction between
logical time and potential causality. We argued that the applications
that require logical time are very different from those that require
potential causality. Further, while logical time tries to approximate
real time order, potential causality tries to approximate true
causality. Real time and true causality lie on opposite ends of a
spectrum of partial orders based on their strictness, as illustrated in
figure~\ref{spectrum-fig}. While happened before is a good model for
logical time, it is not an accurate model for potential causality.

We defined the {\em potentially causes\/} relation, denoted by $\pc$,
to more accurately model potential causality. Two events are said to be
{\em potentially independent\/}, denoted by $\pind$, if they are
incomparable by the potentially causes relation. The potentially causes
relation uses only the causal relationship between events and not their
order in time. If commuting the order of two events would have no
effect on the computational outcome, they are independent. Thus, the
potential causality model captures independence in a broader sense than
concurrency between totally ordered processes.  Besides allowing
multi-threaded processes to be modeled naturally, it also accomodates
independent calls to a shared library, and independent operations such
as in database systems.

The main impact of the potential causality model is in reducing false
causality that is inherent in the happened before model because of its
requirement that local events be totally ordered. Any application that
requires causality tracking would benefit by reducing the extent of
false causality. We demonstrated this in a number of applications
including predicate detection, race detection, recovery and causal
ordering. We now describe its application in recovery and in our fault
avoidance system.

\subsubsection*{Application 1: Recovery}

\begin{figure}[b]
\centerline{\epsfbox{Figures/recovery.eps}}
\caption{Recovery \label{recovery-fig}}
\end{figure}

We focus on optimistic log-based rollback recovery \cite{ejw96}.  In
figure~\ref{recovery-fig}(a), process $P1$ has failed and has recovered
to state $a$ (using checkpoints and message logs).  In order to
maintain consistency, any events that causally depend on the events on
$P1$ that have been rolled back must also be rolled back. The most
recent consistent global state to which the whole system can roll back
is termed the {\em maximum recoverable state\/}, ($G$ in the figure).
As expected of the happened before model, some events may be
unnecessarily rolled back because of false causality. If the receive
and send events on process $P2$ were independent as in
figure~\ref{recovery-fig}(b), then the {\em maximum recoverable
state\/} can be advanced (to $H$) to avoid unnecessary rollbacks. In
this case, process $P2$ only needs to roll back its receive event and
process $P3$ doesn't need to roll back at all.  To summarize: the potential
causality model requires less rollback during recovery than the
happened before model, and thus results in less wasted work.

A similar argument of reducing unnecessary rollbacks could be used for
coordinated checkpoint based recovery \cite{ejw96}.  We further note
that using potential causality also has  benefits for causal log-based
recovery \cite{ez92, ahm93}. These schemes require a message to carry
its relevant causal history with it. The potential causality model
would identify false causality, and thus reduce the size of the causal
history.

\subsubsection*{Application 2: Fault Avoidance}

\begin{figure}
\centerline{\epsfbox{Figures/avoid-model.eps}}
\caption{Fault Avoidance \label{avoid-model-fig}}
\end{figure}

Consider the scenario shown in figure~\ref{avoid-model-fig}(a). The
fault avoidance system has taken a trace using happened before and has
detected a race condition. The race has occured because two concurrent
segments of computation (marked by bold segments) on the two processes
have tried to access the same shared object. It is now up to the fault
avoidance system to see if the computation can be salvaged by adding
extra synchronizations. However, on inspection it appears that no
matter which segment is executed first, the other segment is forced to
execute concurrently. In reality, there may have been false causality
between $b$ and $c$ in the second process. If, instead, we had used the
potential causality model, we might have detected the independence of
$b$ and $c$ as shown in figure~\ref{avoid-model-fig}(b).  Then we could
add a synchronization from $e$ to $f$ as shown which would ensure that
the race would not occur while the computation is replayed. To
summarize: the potential causality model makes it easier to avoid
synchronization faults by allowing more ordering flexibility in the
trace.

Note that the problem we have just described is also known as
{\em off-line predicate control\/}, and we will discuss it in greater
detail in section~4.

\subsection{Proposed Work: Implementing the Potential Causality Model in
the Fault Avoidance System}

The effectiveness of the potential causality model in practice would
depend on a good causality tracking mechanism (just as vector clocks
have been used to track happened before).  However, in \cite{tg98-tr},
we deferred discussing the implementation of the tracking mechanism
since it would depend largely on the application domain.  As
demonstrated above, the fault avoidance system is an application domain
that requires the use of the potential causality model.  Therefore, we
propose to study techniques to implement causality tracking in the
context of the fault avoidance system. This allows us to investigate
issues in implementing the potential causality model, such as time and
space overheads. Further, it would be a natural requirement of the
fault avoidance system.
