Time-Lapse Snapshots
Authors:
- Cynthia DworkCDCynthia Dwork
- Maurice HerlihyMHMaurice Herlihy
- Serge PlotkinSPSerge Plotkin
- Orli WaartsOWOrli Waarts
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (5) , 1848-1874
Abstract
A snapshot scan algorithm produces an "instantaneous" picture of a region of shared memory that may be updated by concurrent processes. Many complex shared memory algorithms can be greatly simplified by structuring them around the snapshot scan abstraction. Unfortunately, the substantial decrease in conceptual complexity quite often is 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; 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 is enhanced while retaining a simple modular structure: bounded concurrent timestamping and bounded randomized consensus. The resulting timestamping protocol dominates all other currently known timestamping protocols: it matches the speed of the fastest known bounded concurrent timestamping protocol while actually reducing the register size by a logarithmic factor. The resulting randomized consensus protocol matches the computational complexity of the best known protocol that uses only bounded values.Keywords
This publication has 33 references indexed in Scilit:
- Bounded Concurrent Time-StampingSIAM Journal on Computing, 1997
- Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per ProcessorSIAM Journal on Computing, 1996
- Wait-Free Consensus Using Asynchronous HardwareSIAM Journal on Computing, 1994
- Atomic snapshots of shared memoryJournal of the ACM, 1993
- Time- and Space-Efficient Randomized ConsensusJournal of Algorithms, 1993
- Composite registersDistributed Computing, 1993
- Beyond atomic registers: bounded wait-free implementations of nontrivial objectsScience of Computer Programming, 1992
- Fast randomized consensus using shared memoryJournal of Algorithms, 1990
- On the minimal synchronism needed for distributed consensusJournal of the ACM, 1987
- Distributed snapshotsACM Transactions on Computer Systems, 1985