Document Open Access Logo

The Space Complexity of Scannable Objects with Bounded Components

Author Sean Ovens

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.30.pdf
  • Filesize: 0.67 MB
  • 18 pages

Document Identifiers

Author Details

Sean Ovens
  • University of Toronto, Canada

Funding

Support is gratefully acknowledged from the Natural Sciences and Engineering Research Council of Canada under grant RGPIN-2020-04178 and the Ontario Graduate Scholarship (OGS) Program.

Acknowledgements

I thank my advisor, Faith Ellen, for the many helpful discussions and proofreading throughout this project. I also thank the anonymous reviewers for their comments.

Cite As Get BibTex

Sean Ovens. The Space Complexity of Scannable Objects with Bounded Components. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.30

Abstract

A fundamental task in the asynchronous shared memory model is obtaining a consistent view of a collection of shared objects while they are being modified concurrently by other processes. A scannable object addresses this problem. A scannable object is a sequence of readable objects called components, each of which can be accessed independently. It also supports the Scan operation, which simultaneously reads all of the components of the object. In this paper, we consider the space complexity of an n-process, k-component scannable object implementation from objects with bounded domain sizes. If the value of each component can change only a finite number of times, then there is a simple lock-free implementation from k objects. However, more objects are needed if each component is fully reusable, i.e. for every pair of values v, v', there is a sequence of operations that changes the value of the component from v to v'.
We considered the special case of scannable binary objects, where each component has domain {0, 1}, in PODC 2021. Here, we present upper and lower bounds on the space complexity of any n-process implementation of a scannable object O with k fully reusable components from an arbitrary set of objects with bounded domain sizes. We construct a lock-free implementation from k objects of the same types as the components of O along with ⌈n/b⌉ objects with domain size 2^b. By weakening the progress condition to obstruction-freedom, we construct an implementation from k objects of the same types as the components of O along with ⌈n/(b-1)⌉ objects with domain size b.
When the domain size of each component and each object used to implement O is equal to b and n ≤ b^k - bk + k, we prove that 1/2⋅ (k + (n-1)/b - log_b n) objects are required. This asymptotically matches our obstruction-free upper bound. When n > b^k - bk + k, we prove that 1/2⋅ (b^{k-1} - {(b-1)k + 1}/b) objects are required. We also present a lower bound on the number of objects needed when the domain sizes of the components and the objects used by the implementation are arbitrary and finite.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • space complexity
  • lower bound
  • shared memory
  • snapshot object

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873-890, September 1993. URL: https://doi.org/10.1145/153724.153741.
  2. James H. Anderson. Composite registers. Distributed Computing, 6(3):141-154, April 1993. URL: https://doi.org/10.1007/BF02242703.
  3. James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Limited-use atomic snapshots with polylogarithmic step complexity. J. ACM, 62(1):3:1-3:22, 2015. URL: https://doi.org/10.1145/2732263.
  4. James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441-461, 1990. URL: https://doi.org/10.1016/0196-6774(90)90021-6.
  5. James Aspnes and Maurice Herlihy. Wait-free data structures in the asynchronous PRAM model. In Second Annual ACM Symposium on Parallel Algorithms and Architectures, pages 340-349, July 1990. Google Scholar
  6. Hagit Attiya and Faith Ellen. Impossibility Results for Distributed Computing. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2014. URL: https://doi.org/10.2200/S00551ED1V01Y201311DCT012.
  7. Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agreement. Distributed Computing, 8(3):121-132, March 1995. URL: https://doi.org/10.1007/BF02242714.
  8. Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? J. ACM, 41(4):725-763, July 1994. URL: https://doi.org/10.1145/179812.179902.
  9. Hagit Attiya and Ophir Rachman. Atomic snapshots in o(n log n) operations. SIAM J. Comput., 27(2):319-340, 1998. URL: https://doi.org/10.1137/S0097539795279463.
  10. Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with n-k+1 atomic read/write registers. Distrib. Comput., 31(2):99-117, April 2018. URL: https://doi.org/10.1007/s00446-017-0301-7.
  11. J.E. Burns and N.A. Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171-184, 1993. URL: https://doi.org/10.1006/inco.1993.1065.
  12. Tian Ze Chen and Yuanhao Wei. Step-optimal implementations of large single-writer registers. Theoretical Computer Science, 826-827:40-50, 2020. Special issue on OPODIS 2016. URL: https://doi.org/10.1016/j.tcs.2020.04.008.
  13. Faith Ellen, Panagiota Fatourou, and Eric Ruppert. Time lower bounds for implementations of multi-writer snapshots. J. ACM, 54(6):30-es, December 2007. URL: https://doi.org/10.1145/1314690.1314694.
  14. Faith Ellen, Rati Gelashvili, Nir Shavit, and Leqi Zhu. A complexity-based classification for multiprocessor synchronization. Distributed Computing, 33(2):125-144, April 2020. URL: https://doi.org/10.1007/s00446-019-00361-3.
  15. Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Comput., 20(3):165-177, 2007. URL: https://doi.org/10.1007/s00446-007-0042-0.
  16. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. URL: https://doi.org/10.1145/114005.102808.
  17. Jaap-Henk Hoepman and John Tromp. Binary snapshots. In Proceedings of the 7th International Workshop on Distributed Algorithms, WDAG '93, pages 18-25, Berlin, Heidelberg, 1993. Springer-Verlag. Google Scholar
  18. Michiko Inoue and Wei Chen. Linear-time snapshot using multi-writer multi-reader registers. In Gerard Tel and Paul M. B. Vitányi, editors, Distributed Algorithms, 8th International Workshop, WDAG '94, Terschelling, The Netherlands, September 29 - October 1, 1994, Proceedings, volume 857 of Lecture Notes in Computer Science, pages 130-140. Springer, 1994. URL: https://doi.org/10.1007/BFb0020429.
  19. A. Israeli, A. Shaham, and A. Shirazi. Linear-time snapshot implementations in unbalanced systems. Mathematical systems theory, 28(5):469-486, September 1995. URL: https://doi.org/10.1007/BF01185868.
  20. Prasad Jayanti. F-arrays: Implementation and applications. In Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, PODC '02, pages 270-279, New York, NY, USA, 2002. Association for Computing Machinery. URL: https://doi.org/10.1145/571825.571875.
  21. Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for nonblocking implementations. SIAM J. Comput., 30(2):438-456, April 2000. URL: https://doi.org/10.1137/S0097539797317299.
  22. Sean Ovens. The space complexity of scannable binary objects. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 509-519, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465084.3467916.
  23. K. Vidyasankar. Converting lamport’s regular register to atomic register. Inf. Process. Lett., 28(6):287-290, August 1988. URL: https://doi.org/10.1016/0020-0190(88)90175-5.
  24. Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, Eric Ruppert, and Yihan Sun. Constant-time snapshots with applications to concurrent data structures. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '21, pages 31-46, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3437801.3441602.
  25. Leqi Zhu and Faith Ellen. Atomic snapshots from small registers. In Emmanuelle Anceaume, Christian Cachin, and Maria Gradinariu Potop-Butucaru, editors, 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14-17, 2015, Rennes, France, volume 46 of LIPIcs, pages 17:1-17:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.17.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact