Global virtual time approximation with distributed termination detection algorithms
Friedemann Mattern, Anneke A. Schoone, Gérard Tel · Utrecht University Repository (Utrecht University) · 1991
It is shown that distributed termination detection algorithms can be transformed into ecient 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 timewarp 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 boundThe work of H. Mehl is