Adaptive algorithms vs. Time Warp: An analytical comparison

Report
Authors:Srinivasan, Sudhir, Department of Computer ScienceUniversity of Virginia Reynolds, Jr, Department of Computer ScienceUniversity of Virginia
Abstract:

Adaptive synchronization algorithms have been proposed to improve upon purely conservative and purely optimisitic algorithms. Experimental studies have have indeed provided encouraging results. In the spirit of previous analyses, we present the first known analytical comparison of adaptively optimisitic algorithms with the Time Warp protocol. We define a class of adaptive protocols, the asynchronous adaptive waiting protocols (AAWP's) and identify several practical protocols that belong to this class. We show that Time Warp can outperform an AAWP arbitrarily. We describe NPSI adaptive protocols, a sub-class of AAWP's, and specify a member of this sub-class, the Elastic Time Algorithm. We show that this algorithm can outperform Time Warp arbitrarily.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Srinivasan, Sudhir, and Jr Reynolds. "Adaptive algorithms vs. Time Warp: An analytical comparison." University of Virginia Dept. of Computer Science Tech Report (1995).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1995