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.