Design and implementation of algorithms to compute global virtual time (GVT) on shared-memory parallel computers is the topic of this paper. GVT is a mechanism that enables one to identify those computations and information that are not prone to future rollbacks for capturing a consistent snapshot of the state of a system. GVT algorithms are used in the Time Warp synchronization mechanism to perform irrevocable operations.
GVT algorithms were originally defined for message-passing computers, but they also can be used on shared-memory machines. The authors present the design, implementation, and correctness proof of a shared-memory GVT algorithm that assumes a sequentially consistent memory model. They conclude that GVT computation is easier and more straightforward on shared-memory parallel computers than on message-passing machines. People working in distributed systems and parallel computation know that this is true for all the algorithms that imply synchronization and message acknowledgments among processes or processors. The main contribution of the paper seems to be related to the authors’ ability to eliminate, in a nontrivial way, from the previous work on distributed GVT algorithms, those problems originating from the distributed nature of message-passing machines. In this way, they obtain a simpler algorithm that might be used efficiently on multiprocessors.