Our Approach: The Technical Details

We base our animations on Lamport's happened before relation [12] which is defined on primitive actions, each assumed to have a processor-local timestamp, denoted for an event a. Positioning events on their process time-line according to their local timestamps (increasing from left to right), event a event b, denoted a b, iff one of the following conditions holds:

i)

events a and b happen on the same process and

timestamp(a) < timestamp(b) two-lamport-defi.ps

ii)

a is the act of sending a message and b is the act of receiving it (denoted by an arrow from a to b) two-lamport-defii.ps

and

iii)

there is some event c such that and two-lamport-defiii.ps

two-lamport-def-unordered.ps

is defined on primitive events. For our purposes, we extend the definition to nonatomic events, defining three relations --- precedes, parallels, and overlaps --- between abstract events. Other extensions have been proposed [12,1,11,3] but ours has been tailored to the needs of visualization systems. We begin with a relation partially precedes, denoted . Let A and B be sets of events. Informally, if some part of A happens before some part of B or they share a primitive event; formally

i)

and

ii) is closed under transitivity

Using partially precedes we define the three possible relations between two abstract events:

Precedes:

A B iff A B and NOT (B A)

Parallels:

A B iff NOT (A B) and NOT (B A), (alternatively, iff )

Overlaps:

A B iff A B and B A

Precedes captures the notion that one abstract event logically occurs before another. Parallels captures the notion that no logical ordering exists between the events and overlaps captures the notion that the events are logically intertwined (that is, some part of each event must occur before some part of the other).

Our techniques associate with each relation a transformation that assigns animation times. In the case of precedes, we separate the events by assigning animation times so that all elements of the first event complete before any element of the second event begins. In the case of parallels, we assign the the same animation time to the earliest events in each set. The transformation for precedes, for example, separates the striped and solid steps of the SOR program in Figure 3, while the transformation for parallels synchronizes the subevents of each step.

For events related by precedes or parallels, the transformations produce consistent orderings; that is, all processes execute the same sequence of events and the happened before relation remains unchanged. For events related by overlaps, however, we cannot construct consistent reorderings and, thus, we introduce partially consistent orderings in which each process executes a subsequence of its original event sequence and the happened before relation is a subset of the original happened before relation.

We base our partially consistent orderings on a user-selected subset of the events called a perspective. Only events named in the perspective are used in computing ordering relations. Events not named in the perspective and not needed for the display of named events are deleted and the remaining events are reordered in a manner consistent with the computed relations. We might, for example, consider the following behavior where all constituent events of an abstract event are labeled with the same uppercase letter two-overlap-ex3.ps from the partial perspective of Process 1. We would use only the Process 1 primitive events for computing ordering relations and, thus, two-perspective-ex1.ps where circles indicate the events used to compute the ordering. The ordering on Process 1 has been applied to all events, including those on Process 2; abstract event C has been deleted since it does not contain elements in the perspective. Alternatively, the same system can be decomposed from the perspective of Process 2, in which case two-perspective-ex2.ps Each reordering is meaningful; each exposes the order of events on an individual process and provides some insight to the code and environment of that process. The two reorderings together characterize the complete behavior of the system.

Further details of the transformation algorithms can be found in [9] and [10].