A Theory of Distributed Time

Natural intuition organizes experience into a linear sequence of discrete events, but this approach is inappropriate for asynchronous distributed systems, where information is distributed and perception is delayed. Distributed environments require a distributed notion of time, to abstract away not only irrelevant physical detail but also irrelevant temporal and computational detail. By expressing distributed systems concepts that are difficult to talk about in terms of real time and by distinguishing what really "happens" from what physically occurred, a theory of distributed time would provide a natural framework for solving problems in distributed environments. This paper lays the groundwork for that claim by formally building such a theory. This research improves on previous work on time in distributed systems by supporting temporal relations more general than partial orders, by supporting abstraction through multiple levels of temporal relations, by separating the family of temporal relations an application consults from the particular clock implementations that track them, and by providing a single arena to consider these issues for a wide range of applications.