BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-92-1423
       ENTRY:: November 5, 1993
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Time-lapse snapshots
        TYPE:: Technical Report
       PAGES:: 20
      AUTHOR:: Dwork, Cynthia
      AUTHOR:: Herlihy, Maurice
      AUTHOR:: Plotkin, Serge A.
      AUTHOR:: Waarts, Orli
    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
               algorithm.
               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.
       NOTES:: [Adminitrivia V3/ACK19940321 Added the ORGANIZATION and
               TYPE information]
               [Adminitrivia V2/ACK/19931216 Reformat authors to
               last-name, first-name.]
               [Adminitrivia V1/ACK/19931105]
         END:: STAN//CS-TR-92-1423