Report Number: CS-TR-92-1423
Institution: Stanford University, Department of Computer Science
Title: Time-lapse snapshots
Author: Dwork, Cynthia
Author: Herlihy, Maurice
Author: Plotkin, Serge A.
Author: Waarts, Orli
Date: November 1993
Abstract: Abstract. A snapshot scan algorithm takes an "instantaneous"
picture of a region of shared memory that may he updated by
concurrent processes. Many complex shared memory algorithms
can be greatly simplified by structuring them around the
snapshot scan abstraction. Unforinnately, the substantial
decrease in conceptual complity is quite often counterbalanced
by an increase in computational complexity.
In this paper, we introduce the notion of a weak snapshot scan,
a slightly weaker primitive that has a more efficient
implementation. We propose the following methodology for using
this abstraction: first, design and verify an algorithm using
the more powerful snapshot scan, and second, replace the more
powerful but less efficient snapshot with the weaker but more
efficient snapshot, and show that the weaker abstraction
nevertheless suffices to ensure the correctness of the enclosing
We give two examples of algorithms whose performance can be
enhanced while retaining a simple modular structure: bounded
concurrent timestamping, and bounded randomized consensus. The
resulting timestamping protocol is the fastest known bounded
concurrent timestamping protocol. The resulting randomized
consensus protocol matches the computational complexity of the
best known protocol that uses only bouned values.