Global Virtual Time Approximation with Distributed Termination Detection
Algorithms
Technical Report RUU-CS-91-32, Department of Computer Science, University
of Utrecht, The Netherlands, 1991
It is shown that distributed termination detection algorithms can be
transformed into efficient 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 exemplified for two termination
detection algorithms, namely an algorithm by Dijkstra et al. and a new scheme
based on the principle of "sticky flags". 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
specific lower bound on the current GVT value. In a straightforward way, the
possibly infinite bundle of parallel termination detection algorithms can be
combined into a single distributed algorithm which computes a tight lower
bound on the GVT.