Vector time and causality among abstract events in distributed computations

T. Basten, T.H. Kunz, J.P. Black, M.H. Coffin, D.J. Taylor

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)


An important problem in analyzing distributed computations is the amount of information. In event-based models, 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. Following Lamport [24], two causality relations are defined on abstract events, called weak and strong precedence. A general theoretical framework based on logical vector time is developed in which several meaningful timestamps for abstract events are derived. 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 schemes used for characterizing weak precedence. We explain why such a simplification seems not possible for strong precedence.
Original languageEnglish
Pages (from-to)21-39
Number of pages19
JournalDistributed Computing
Issue number1
Publication statusPublished - 1997


Dive into the research topics of 'Vector time and causality among abstract events in distributed computations'. Together they form a unique fingerprint.

Cite this