Time and the Order of Abstract Events in Distributed Computations

An important problem in event-based models of distributed computations is the amount of behavioral information. Even for simple applications, the number of events is large and the causal structure is complex. Event abstraction can be used to reduce the apparent complexity of a distributed computation.

This paper discusses one important aspect of event abstraction: causality among abstract events. Logical vector time and a derived notion called reversed vector time can be used to assign two meaningful timestamps to abstract events. These timestamps can be used to efficiently determine causal relationships between arbitrary abstract events.

The class of convex abstract events is identified as a subclass of abstract events that is general enough to be widely applicable and restricted enough to simplify timestamping. For this class, ordinary vector time is sufficient to determine causal relationships. At the cost of some extra computational effort, the timestamps derived for convex abstract events can also be used for arbitrary abstract events, overcoming the need for reversed timestamping.

(The full version is not available because the paper is superseded by the following publication)

Back to the list of Technical Reports.