Event-based behavioral abstraction has two main components: the modeling language it provides the user in order to model the the intended behavior of the program, and the feedback scheme it employs to guide the user to understand the actual system behavior. The two services are interdependent - the more expressive the modeling language is, less detailed becomes the feedback that the debugger can provide. Three kinds of modeling language have been proposed: those based on variants of regular expressions [19][22][6][5], those based on temporal logic- [17] or process algebra-oriented specifications [4], and those based on extension of database query languages [][41]. Modeling languages can be qualitatively compared along two main components: representation of program behavior, and interpretation of model matching with behaviors.
Representation of Behavior: Often, behavior is represented as a string of events (imposing a total ordering among the observed events) [41][4][17][44][19][5][6]. It can also be described, more appropriately, as a partial order of events based on Lamport's happened before relation [20][22]. String representation obscures some temporal ordering relationship, by imposing an arbitrary total order on a partially ordered graph, and thus making them sensitive to change in process speeds (perturbations due to physical asynchrony).
Matching Interpretation: A model can be matched to a behavior in different ways. Baiardi et al [4], Zave [44] requires the model to match all input events: no skipping of events is allowed. This can be thought of as parsing approach. Another alternative [5][19] is to use a pattern extraction approach where events are skipped as needed. Hough [20] illustrates the difference between the two approaches with the following figure.
The two approaches reflect two extreme points of a spectrum.
With parsing, an error can be uniquely identified: but the user
has to account for all low level events in the model description.
With pattern extraction, the user has a very flexible modeling
interface, but the unrestrained filtering during matching gives rise
to our first concern with event-based abstraction whereby the
debugger restricts its feedback to a match/mismatch vocabulary.
In Figure 
, the parsing approach can flag an
error as soon as it encounters the first 
event. No such
unique error event exists when the matching interpretation is that
of pattern extraction.
Ariadne uses a simple modeling language based on regular expression that
uses Lamport's happened before graph as internal representation of the
behavior.
The vertices of the graph represent events, and there is a directed edge
from vertex 
to vertex 
iff
This graph is called the partial order execution graph (POEG).
A parsing approach to matching semantics is employed. We resolve the tension between the expressivity of modeling language, and the feedback vocabulary in favor of the latter, and as a result, provide a powerful vehicle for systematic debugging of parallel programs.