Virtual time and global states of distributed systems.

Abstract 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 r e al 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 m o del of time which consists of vectors of clocks. These clock-vectors are p artially ordered and form a lattice. By using timestamps and a simple clock update mechanism the structure o f c ausality is represented in an isomorphic way. The new model of time has a close analogy to Minkowski's relativistic spacetime 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 r e c eived out of order