Abstract: In distributed systems it is often important to be able to determine the temporal relationships between events generated by different processes. An algorithm to determine such relationships is presented by Fidge and Mattern. This algorithm has many favorable attributes such as it allows for any kind of interprocess communication, and it requires no extra synchronization messages, additional communication links or central timestamping authority. The algorithm, however, requires O(n) space for each process (where n is the number of processes). i.e., it requires an overall space of O(n^2). This can be a large overhead especially when there are a very large number of processes.
By cutting down on this generality, we can significantly decrease the amount of space required to determine temporal relationships. In this paper, we show how one may reduce the space requirements by assuming that the communication links between processes is static and known ahead of time; and also that one is interested only in determining the temporal ordering between messages arriving at the same process. We argue that these assumptions are reasonable to make for a large class of problems.