The Ariadne Modeling Language

As mentioned above, previous attempts at using event-based abstraction in debugging have been limited by the complexity of the modeling language. Ariadne's language is quite simple. It employs a three level description of communication patterns in terms of chains, p-chains, and pt-chains.

• Chains are patterns representing ``local views'' of communication. They are described by extensions of regular expressions. When they are matched against an execution history graph, all events in the chain must occur exactly in the order specified with the exception of communication events that are not physically realized because of ``edge effects'' on process array boundaries [1].

• p-Chains are patterns representing the concurrent execution of a chain by a set of processes. They are described by binding a chain to a process set. When a p-chain is matched against a behavior, a copy of its chain is matched on each element of its process set (events can be shared across, but not within, chains).

• pt-Chains are patterns representing the logical, temporal composition of a set of p-chains. They are matched in a two step process: first events matching the p-chains are located in the graph and then the specified logical relations between those events are verified. When a pt-chain has been successfully matched, it returns an abstract event which is a structure containing the matched instances of events; these instances are removed from the trace and are unavailable for further matching unless explicitly restored.

These three definitional levels appear to form a natural mechanism for describing parallel systems, as evidenced by their use in other contexts such as the XYZ levels of Phase Abstractions [24] and the LaRCS specification language [22]. The matching algorithm for our language is straightforward: a pt-chain is recognized by a finite state machine that invokes copies of other finite state machines to recognize chains on specific processes. This matching can be done efficiently, avoiding the costliness of pattern matching approaches [3,13] and the expensive implementations of previous languages [16]. At the same time, our matching algorithm can provide precise information on the reasons for a match failure.