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 in [3] and [5]. 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 interest...
No takes yet. Share an insight, caveat, or question.
Meldal et al. (1991) studied this question.