Adaptive algorithms vs. Time Warp: an analytical comparison

Adaptive synchronization algorithms have been proposed to improve upon conservative and optimistic algorithms. We present the first known analytical comparison of adaptive, optimistic algorithms and Time Warp. We define a class of adaptive protocols, the asynchronous adaptive waiting protocols (AAWPs) and identify several practical protocols that belong to this class. We show that Time Warp can outperform an AAWP arbitrarily. We describe the Elastic Time Algorithm (ETA), a particular AAWP and show that ETA can outperform Time Warp arbitrarily