Virtual Time and Global States of Distributed Systems 

In: Cosnard M. et al. (eds): Proc. Workshop on Parallel and Distributed 
Algorithms, North-Holland / Elsevier, pp. 215-226, 1989 (Reprinted in: Z. 
Yang, T.A. Marsland (eds.), "Global States and Time in Distributed Systems", 
IEEE, 1994, pp. 123-133.) 

A distributed system can be characterized by the fact that the global state 
is distributed and that a common time base does not exist. However, the 
notion of time is an important concept in every day life of our decentralized 
"real world" and helps to solve problems like getting a consistent 
population census or determining the potential causality between events. We 
argue that a linearly ordered structure of time is not (always) adequate for 
distributed systems and propose a generalized non-standard model of time which 
consists of vectors of clocks. These clock-vectors are partially ordered and 
form a lattice. By using timestamps and a simple clock update mechanism the 
structure of causality is represented in an isomorphic way. The new model of 
time has a close analogy to Minkowski's relativistic space-time and leads 
among others to an interesting characterization of the global state problem. 
Finally, we present a new algorithm to compute a consistent global snapshot of 
a distributed system where messages may be received out of order.