Understanding Distributed Program Behavior Using a Multicast Communication Scheme

Abstract

Events in a distributed global computation framework, unlike those in a sequential local computation, form a partially ordered set with respect to the causality relation revealed by timestamps. This paper describes a new logical timestamping mechanism based on multicasting, called Collective Logical Time, and compares it with other known schemes that have been eveloped in the domain mainly to help in detecting undesired (global) properties of distributed computations (such as deadlock). Unfortunately, due to excessive complexity and some unrealistic restrictions (such as a fixed number of processes), these schemes have produced limited results. Some of the benefits in using our scheme are revealed, together with the possibilities for direct applications in the development of low-level communication protocols.