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.