T. Basten and T. Kunz and J.P. Black and M.H. Coffin and D.J. Taylor. Time and the Order of Abstract Events in Distributed Computations. Eindhoven University of Technology, Department of Mathematics and Computing Science, Eindhoven, The Netherlands. Computer Science Note. Number 94/06. Feburary 1994.


Abstract

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.


Back to Shoshin Group Publications Home Page (Technical reports)...