skip to main content
10.1145/1281100.1281108acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CAS

Published: 12 August 2007 Publication History

Abstract

Snapshots are fundamental shared objects which provide consistent views of blocks of shared memory. A snapshot object consists of an array of m memory cells and allows processes to execute UPDATES to write new values in any of the snapshot cells, and SCANS to return consistent views of all m cells. An interesting (weaker) form of snapshot with several applications is a single-scanner snapshot which allows to only one process, called scanner, to execute SCANS (UPDATES can still be executed concurrently).
We present the first time-optimal, single-scanner snapshot implementations from read-write registers for an asynchronous system of n processes. Our first algorithmis very simple and has time complexity O(1) for UPDATE and O(m) for SCAN, which is optimal. However, in systems with no garbage collector, the number of registers it uses is proportional to the number of executed SCANS. Our second implementation employs an interesting recycling technique to reduce the space complexity to O(mn) bounded-size registers still achieving optimal time complexities for both operations. These algorithms are simple and practical, and improve upon all previous algorithms in terms of time and space complexity. For systems that provide stronger primitives, like Compare-And-Swap (CAS), we provide a multi-scanner snapshot implementation that uses m+1 CAS registers and m read-write registers, and has time complexity O(1)for UPDATE and O(m) for SCAN.

References

[1]
Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. J. of the ACM, 40(4):873--890, Sept. 1993.
[2]
J. H. Anderson. Composite registers. Distributed Computing, 6(3):141--154, Apr. 1993.
[3]
J. H. Anderson. Multi-writer composite registers. Distributed Computing, 7(4):175--195, 1994.
[4]
J. Aspnes. Time- and space-efficient randomized consensus. J. of Algorithms, 14(3):414--431, May 1993.
[5]
J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In Proc. of the 2nd ACM Symp. on Parallel Algorithms and Architectures, pp. 340--349, 1990.
[6]
H. Attiya, F. Ellen, and P. Fatourou. The Complexity of Updating Multi-writer Snapshot Objects. In Proc. of 8th Int. Conf. on Distributed Computing and Networking, pp. 319--330, Dec. 2006.
[7]
H. Attiya and A. Fouren. Adaptive and Efficient Algorithms for lattice agreement and renaming. SICOMP, 31(2):642--664, Oct. 2001.
[8]
H. Attiya, M. Herlihy, and O. Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8:121--132, 1995.
[9]
H. Attiya, N. Lynch, and N. Shavit. Are wait-free algorithms fast? J. of the ACM, 41(4):725--763, 1994.
[10]
H. Attiya and O. Rachman. Atomic snapshots in O(n log n) operations. SICOMP, 27(2):319--340, 1998.
[11]
C. Dwork, and O. Waarts. Simple and Efficient Bounded Concurrent Timestamping and the Traceable Use Abstraction. J. of the ACM, 46(5):633--666, Sept. 1999.
[12]
P. Fatourou, F. Fich, and E. Ruppert. Space-optimal multi-writer snapshot objects are slow. In Proc. of the 21th ACM Symp. on Principles of Distributed Computing, pp. 13--20, 2002.
[13]
P. Fatourou, F. Fich, and E. Ruppert. A tight time lower bound for space-optimal implementations of multi-writer snapshots. In Proc. of the 35th ACM Symp. on Theory of Computing, pp. 259--268, 2003.
[14]
P. Fatourou, F. Fich, and E. Ruppert. Time-space tradeos for implementations of snapshots. In Proc. of the 38th ACM Symp. on Theory of Computing, pp. 169--178, 2006.
[15]
P. Fatourou, and N. D. Kallimanis. Single-Scanner Snapshot Implementations are Fast! In Proc. of the 25th ACM Symp. on Principles of Distributed Computing, pp. 228--237, July 2006.
[16]
P. Fatourou, and N. D. Kallimanis. Time-Optimal, Space-Efficient Single-Scanner Snapshots & Efficient Multi-Scanner Snapshots using CAS. Technical Report TR 2007-02, Department of Computer Science, University of Ioannina, February 2007.
[17]
R. Gawlick, N. Lynch, and N. Shavit. Concurrent timestamping made simple. In Proc. of the Israel Symp. on the Theory of Computing and Systems, LLNCS # 601, pp. 171--183, 1992.
[18]
S. Haldar. Efficient bounded timestamping using traceable use abstraction | Is writer's guessing better than reader's telling? Technical Report RUU-CS-93-28, Department of Computer Science, Utrecht University, September 1993.
[19]
M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. on Programming Languages and Systems, 12(3):463--492, July 1990.
[20]
M. Inoue, W. Chen, T. Masuzawa, and N. Tokura. Linear time snapshots using multi-writer multi-reader registers. In 8th Int. Workshop on Distributed Algorithms, LLNCS # 857, pp. 130--140, 1994.
[21]
A. Israeli, A. Shaham, and A. Shirazi. Linear-time snapshot implementations in unbalanced systems. Mathematical Systems Theory, 28(5):469--486, Sept./Oct. 1995.
[22]
P. Jayanti. f-Arrays: Implementation and Applications. In Proc. of the 21th ACM Symp. on Principles of Distributed Computing, pp. 270--279, 2002.
[23]
P. Jayanti. An Optimal Multi-writer Snapshot Algorithm. In Proc. of the 37th ACM Symp. on Theory of Computing, pp. 723--732, 2005.
[24]
P. Jayanti, and S. Petrovic. Efficient wait-free implementation of multiword ll/sc variables. In Proc. of the 25th Int. Conf. on Distributed Computing Systems, pp. 59--68, 2005.
[25]
P. Jayanti, K. Tan, and S. Toueg. Time and Space Lower Bounds for non-blocking implementations. SICOMP, 30(2):438--456, June 2000.
[26]
L. M. Kirousis, P. Spirakis, and P. Tsigas. Reading many variables in one atomic operation: solutions with linear or sublinear complexity. IEEE Trans. Parallel and Distributed Systems, 5(7):688--696, 1994.
[27]
S. Mullender. Distributed Systems. Addison-Wesley, 1994.
[28]
G. Peterson. Concurrent reading while writing. ACM Trans. on Programming Languages and Systems, 5(1):46--55, 1983.
[29]
Y. Riany, N. Shavit, and D. Touitou. Towards a practical snapshot algorithm. Theoretical Computer Science, 269(1-2):163--201, 2001.

Cited By

View all
  • (2023)Exploring Trade-Offs in Partial Snapshot ImplementationsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_8(90-105)Online publication date: 30-Sep-2023
  • (2021)Constant-time snapshots with applications to concurrent data structuresProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441602(31-46)Online publication date: 17-Feb-2021
  • (2013)Lock-Free Data-Structure IteratorsProceedings of the 27th International Symposium on Distributed Computing - Volume 820510.1007/978-3-642-41527-2_16(224-238)Online publication date: 14-Oct-2013
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing
August 2007
424 pages
ISBN:9781595936165
DOI:10.1145/1281100
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. asynchronous
  2. compare-and-swap (CAS)
  3. distributed algorithms
  4. linearizable objects
  5. single-scanner
  6. snapshots
  7. wait-free implementations

Qualifiers

  • Article

Conference

PODC07

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Exploring Trade-Offs in Partial Snapshot ImplementationsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_8(90-105)Online publication date: 30-Sep-2023
  • (2021)Constant-time snapshots with applications to concurrent data structuresProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441602(31-46)Online publication date: 17-Feb-2021
  • (2013)Lock-Free Data-Structure IteratorsProceedings of the 27th International Symposium on Distributed Computing - Volume 820510.1007/978-3-642-41527-2_16(224-238)Online publication date: 14-Oct-2013
  • (2011)The complexity of updating snapshot objectsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2011.08.00271:12(1570-1577)Online publication date: 1-Dec-2011
  • (2010)Experimenting Iterative Computations with Ordered Read-Write LocksProceedings of the 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing10.1109/PDP.2010.11(155-162)Online publication date: 17-Feb-2010
  • (2010)Iterative computations with ordered read-write locksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2009.09.00270:5(496-504)Online publication date: 1-May-2010
  • (2008)Partial snapshot objectsProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378591(336-343)Online publication date: 1-Jun-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media