Programmers are often confused by the results of asynchronous executions
because they do not foresee all possible interleavings of events. In fact,
most of these interleavings are arbitrary and irrelevant: program
correctness depends only on the event orderings imposed by data
dependencies. Thus, we are interested in the ordering of events not in
physical time but in logical time. At the primitive event level, this
ordering is captured by Lamport's happened before relation. We extend
Lamport's relation to sets of primitive events;
defining three relations: precedes, parallels, and overlaps [21] for use in the
construction of pt-chains. Informally, if 
and 
are sets of
primitive events,
then
precedes
(denoted 
) iff
there is some dependency from an event in to an event in but
no dependency from an event in to an event in ,
parallels (denoted 
) iff there is no
dependency from any event in to an event in and no dependency
from any event in to an event in , and
overlaps (denoted 
) iff
there is both a dependency from an event in to an event in and
a dependency from an event in to an event in .
In the Binary Image Compression example, each communication step
strictly precedes the next. This behavior, for a 32 process system,
can be described as
where the angular brackets around compr* in the last statement signals that precedes relation holds between successive iterations of the communication phase. Similar extensions have previously been proposed [27][22][16][11] but we have found our definitions to be more appropriate for debugging. In particular, our precedes relation captures the notion that just some part of a complex event happens before some part of another event; other definitions require a total ordering which is rarely found among the higher-level abstract events in the programs we have examined.
Ariadne's modeling language allows users to specify behavior at a coarse level, in order to retain the simplicity and the feedback capability. Query facilities are designed to ``walk'' the match tree, and investigate different portions of the execution history. Selecting different portions of the execution through abstract events becomes difficult with a solely textual interface. To circumvent this, and to make the environment user-friendly we decided to visualize the match tree in a scalable fashion.
