On the Relativistic Structure of Logical Time in Distributed Systems
In: Datation et Controle des Executions Reparties, Bigre 78 (ISSN 0221-525),
pp. 3-20, 1992
A distributed system, where processes communicate via messages with
unpredictable transmission times, is characterized by the fact that no process
has an up-to-date and consistent view of the system's global state.
Furthermore, the notion of global time does not exist a priori within such a
system. However, by defining time to be a partially ordered set of vectors
forming a lattice structure, one gets a notion of logical time which is
realizable in such a system and which represents the causality structure of
events in an isomorphic way. With this definition, the relations "later" and
"at the same time" get a new and generalized but adequate interpretation.
Interestingly, it turns out that this notion of time is similar in structure
to Minkowski's relativistic space-time model. We motivate the concept of
"vector time", elaborate its properties, and discuss the analogy to
relativistic space-time.