Global Virtual Time Approximation with Distributed Termination Detection Algorithms

It is shown that distributed termination detection algorithms can be transformed into e cient algorithms to approximate the so-called Global Virtual Time (GVT) of a distributed monotonic computation. Typical instances of such computations are optimistic distributed simulations based on the time-warp principle. The transformation is exempli ed for two termination detection algorithms, namely an algorithm by Dijkstra et al. and a new scheme based on the principle of \sticky ags". The general idea of the transformation is that many termination detection algorithms (viz., one for each possible GVT value) run in parallel. Each algorithm determines a speci c lower bound on the current GVT value. In a straightforward way