next up previous
Next: Ariadne Queries Up: Our Approach Previous: The Ariadne Modeling

Logical Time Manipulation in Ariadne

Programmers are often confused by the results of asynchronous executions because they can not foresee all possible interleavings of events. In fact, most of these interleavings are irrelevant: the programmer does not care about the arbitrary orderings of events by physical time. Instead, the programmer is concerned with the logical ordering of events. At the primitive event level, this ordering is captured by Lamport's happened before relation. Other debuggers have used temporal logic to express assertions about happened before [6,10] but they do not use behavioral abstraction. We extend the relation to abstract events, defining three relations: precedes, parallels, and overlaps [15]. Informally, if A and B are abstract events, then

precedes (denoted ) iff there is some dependency from an event in A to an event in B but no dependency from an event in B to an event in A,

parallels (denoted A||B) iff there is no dependency from an event in A to an event in B and no dependency from an event in B to an event in A, and

overlaps (denoted ) iff there is both a dependency from an event in A to an event in B and a dependency from an event in B to an event in A.

Similar extensions have been proposed [8,16,18] 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 in the programs we have examined.

Abstract events may interact in complex ways and often the programmer wishes to focus on particular aspects of that interaction, excluding all other aspects. Thus, for example, when debugging a program that used a parallel queue, we were surprised to find that the overlaps relation held between Insert and Delete operations on the same queue location. This interdependence was the result of logical orderings imposed by the mechanisms used to resolve competition for queue locations; these orderings had nothing to do with the correctness of the implementation. When we asked the debugger to ignore all orderings except those imposed by accesses to queue locations, we were able to correctly interpret the behavior of the program [7]. Ariadne, like our previous debugger, allows the user to selectively ignore some logical orderings and thus manipulate logical time to create different perspectives on program behavior [15].



next up previous
Next: Ariadne Queries Up: Our Approach Previous: The Ariadne Modeling



Joydip Kundu kundu@neweng.enet.dec.com