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

Single-scanner multi-writer snapshot implementations are fast!

Published: 23 July 2006 Publication History

Abstract

Snapshot objects allow processes to obtain consistent global views of shared memory. A snapshot object consists of m components each capable of storing a value. The processes execute UPDATE operations to write new values in any of the components and SCANS to obtain consistent views of the snapshot contents. A single-scanner snapshot object supports only one active SCAN at any point in time (although UPDATES can still be executed concurrently).This paper studies wait-free, linearizable, single-scanner, multi-writer snapshot implementations from registers in an asynchronous shared-memory system, and presents a collection of upper and lower bounds on their complexity. We provide the first such implementations with time complexities that are (linear or quadratic) functions only of the number of snapshot components and not of the number of processes. Moreover, we argue that single-scanner implementations require at least m registers and we prove that, for such implementations which are space-optimal, SCANS execute Ω(m2) steps.Our results reveal that a lower bound derived for the multi-scanner case can be beaten when we restrict the number of concurrently active SCANS. When m is constant, our algorithms exhibit constant time complexity (while one of them requires a constant number of registers as well). For the design of our algorithms we employ new ideas, while the proof of their correctness is a complicated task.

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, September 1993.
[2]
Y. Afek, G. Stupp, and D. Touitou. Long-lived and adaptive collect with applications. In Proc. of the 40th IEEE Symposium on Foundations of Computer Science pages 262--272, October 1999.
[3]
Y. Afek, G. Stupp, and D. Touitou. Long-lived and adaptive atomic snapshot and immediate snapshot. In Proc. of the 19th Annual ACM Symposium on Principles of Distributed Computing pages 71--80, July 2000.
[4]
J. H. Anderson. Composite registers. Distributed Computing 6(3):141--154, April 1993.
[5]
J. H. Anderson. Multi-writer composite registers. Distributed Computing 7(4):175--195, May 1994.
[6]
J. Aspnes. Time-and space-efficient randomized consensus. J. of Algorithms 14(3):414 . 431, May 1993.
[7]
J. Aspnes and M. Herlihy. Fast, randomized consensus using shared memory. J. of Algorithms 11(2):441--46, September 1990.
[8]
J. Aspnes and M. Herlihy. Wait-free data structures in the asynchronous PRAM model. In Proc. of the 2nd ACM Symposium on Paral lel Algorithms and Architectures pages 340--349, July 1990.
[9]
H. Attiya, F. Fich, and Y. Kaplan. Lower bounds for adaptive collect and related objects. In Proc. of the 23th Annual ACM Symposium on Principles of Distributed Computing pages 60--69, July 2004.
[10]
H. Attiya and A. Fouren. Algorithms adaptive to point contention. J. ACM 50(4):444--468, July 2003.
[11]
H. Attiya, A. Fouren, and E. Gafni. An adaptive collect algorithm with applications. Distributed Computing 15(2):87--96, April 2002.
[12]
H. Attiya, N. Lynch, and N. Shavit. Are wait-free algorithms fast? J. of the ACM 41(4):725--763, July 1994.
[13]
H. Attiya and O. Rachman. Atomic snapshots in O (n log n) operations. SIAM J. Comput. 27(2):319--340, April 1998.
[14]
H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edition Wiley, 2004.
[15]
A. Brodsky and F. Fich. E . cient synchronous snapshots. In Proc. of the 23th Annual ACM Symposium on Principles of Distributed Computing pages 70--79, July 2004.
[16]
J. Burns and N. Lynch. Bounds on shared memory for mutual exclusion. Information and Computation 107(2):171--184, December 1993.
[17]
D. Dolev and N. Shavit. Bounded concurrent time-stamping. SIAM J. on Computing 26(2):418--445, 1997.
[18]
P. Fatourou, F. Fich, and E. Ruppert. Space-optimal multi-writer snapshot objects are slow. In Proc. of the 21th Annual ACM Symposium on Principles of Distributed Computing pages 13--20, July 2002.
[19]
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 Annual ACM Symposium on Theory of Computing pages 259--268, June 2003.
[20]
P. Fatourou, F. Fich, and E. Ruppert. Time-space tradeoffs for implementations of snapshots. In Proc. of the 38th Annual ACM Symposium on Theory of Computing May 2006.
[21]
R. Gawlick, N. Lynch, and N. Shavit. Concurrent timestamping made simple. In Proc. of the Israel Symposium on the Theory of Computing and Systems volume 601 of LNCS pages 171--183, May 1992.
[22]
R. Guerraoui, M. Herlihy, and B. Pochon. Polymorphic contention management. In Proc. of the 19th International Symposium on Distributed Computing pages 303--323, September 2005.
[23]
R. Guerraoui, M. Herlihy, and B. Pochon. Toward a theory of transactional contention managers. In Proc. of the 24th ACM Symposium on Principles of Distributed Computing pages 258--264, July 2005.
[24]
R. Guerraoui and E. Ruppert. What can be implemented anonymously? In Proc. of the 19th International Symposium on Distributed Computing volume 3724 of LNCS pages 244--259, September 2005.
[25]
M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer. Software transactional memory for dynamic-sized data structures. In Proc. of the 22th ACM Symposium on Principles of Distributed Computing pages 92--101, July 2003.
[26]
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.
[27]
M. Inoue, W. Chen, T. Masuzawa, and N. Tokura. Linear time snapshots using multi-writer multi-reader registers. In Distributed Algorithms, 8th International Workshop volume 857 of LNCS pages 130--140, April 1994.
[28]
A. Israeli and M. Li. Bounded timestamps. Distributed Computing 6(4):205--209, July 1993.
[29]
A. Israeli, A. Shaham, and A. Shirazi. Linear-time snapshot implementations in unbalanced systems. Mathematical Systems Theory 8(5):469--486, September/October 1995.
[30]
L. M. Kirousis, P. Spirakis, and P. Tsigas. Reading many variables in one atomic operation: solutions with linear or sublinear complexity. IEEE Trans. on Parallel and Distributed Systems 5(7):688--696, July 1994.
[31]
L. Lamport. A fast mutual exclusion algorithm. ACM Trans. on Computer Systems 5(1):1--11, January 1987.
[32]
N. A. Lynch. Distributed Algorithms Morgan Kaufmann, 1996.
[33]
S. Mullender. Distributed Systems Addison-Wesley, 1994.
[34]
Y. Riany, N. Shavit, and D. Touitou. Towards a practical snapshot algorithm. Theoretical Computer Science 269(1--2):163--201, 2001.
[35]
W. N. Scherer and M. Scott. Advanced contention management for dynamic software transactional memory. In Proc. of the 24th ACM Symposium on Principles of Distributed Computing pages 240--248, July 2005.
[36]
H. Sundell, P. Tsigas, and Y. Zhang. Simple and fast wait-free snapshots for real-time systems. In Proc. of the 4th International Conference On Principles Of DIstributed Systems pages 91--106, July 2000.

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
  • (2022)Design Eye-Tracking Augmented Reality Headset to Reduce Cognitive Load in Repetitive Parcel Scanning TaskIEEE Transactions on Human-Machine Systems10.1109/THMS.2022.317995452:4(578-590)Online publication date: Aug-2022
  • (2016)Snapshots in Shared MemoryEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_380(2017-2022)Online publication date: 22-Apr-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
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: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. asynchronous
  2. atomic objects
  3. multi-writer
  4. shared memory systems
  5. single-scanner
  6. snapshot
  7. wait-free

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 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
  • (2022)Design Eye-Tracking Augmented Reality Headset to Reduce Cognitive Load in Repetitive Parcel Scanning TaskIEEE Transactions on Human-Machine Systems10.1109/THMS.2022.317995452:4(578-590)Online publication date: Aug-2022
  • (2016)Snapshots in Shared MemoryEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_380(2017-2022)Online publication date: 22-Apr-2016
  • (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
  • (2007)Time-optimal, space-efficient single-scanner snapshots & multi-scanner snapshots using CASProceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing10.1145/1281100.1281108(33-42)Online publication date: 12-Aug-2007
  • (2006)The complexity of updating multi-writer snapshot objectsProceedings of the 8th international conference on Distributed Computing and Networking10.1007/11947950_35(319-330)Online publication date: 27-Dec-2006

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