Document Open Access Logo

Progress-Space Tradeoffs in Single-Writer Memory Implementations

Authors Damien Imbs, Petr Kuznetsov, Thibault Rieutord

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.9.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Damien Imbs
Petr Kuznetsov
Thibault Rieutord

Cite As Get BibTex

Damien Imbs, Petr Kuznetsov, and Thibault Rieutord. Progress-Space Tradeoffs in Single-Writer Memory Implementations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.9

Abstract

Many algorithms designed for shared-memory distributed systems assume the single-writer multi- reader (SWMR) setting where each process is provided with a unique register that can only be written by the process and read by all. In a system where computation is performed by a bounded number n of processes coming from a large (possibly unbounded) set of potential participants, the assumption of an SWMR memory is no longer reasonable. If only a bounded number of multi- writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, implementing an SWMR memory, or equivalently, ensuring stable writes (i.e., every written value persists in the memory), is desirable.
In this paper, we propose an SWMR implementation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses n + k − 1 registers to implement a k-lock-free SWMR memory. In the special case of 2-lock-freedom, we also give a matching lower bound of n + 1 registers, which supports our conjecture that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR implementations might coincide.

Subject Classification

Keywords
  • Single-writer memory implementation
  • comparison-based algorithms
  • space complexity
  • progress conditions

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, 1993. URL: http://dx.doi.org/10.1145/153724.153741.
  2. Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. J. ACM, 37(3):524-548, 1990. URL: http://dx.doi.org/10.1145/79147.79158.
  3. Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous obstruction-free (n, k)-set agreement with n-k+1 atomic read/write registers. In 19th International Conference on Principles of Distributed Systems, OPODIS '15, pages 18:1-18:17, 2015. Google Scholar
  4. James E Burns and Nancy A Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171-184, 1993. Google Scholar
  5. Victor Bushkov and Rachid Guerraoui. Safety-liveness exclusion in distributed computing. In 34th ACM Symposium on Principles of Distributed Computing, PODC '15, pages 227-236, 2015. Google Scholar
  6. Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport. Adaptive register allocation with a linear number of registers. In International Symposium on Distributed Computing, DISC '13, pages 269-283, 2013. Google Scholar
  7. Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Black art: Obstruction-free k-set agreement with |mwmr registers| less |proccesses|. In 1st International Conference on Networked Systems, NETYS '13, pages 28-41, 2013. Google Scholar
  8. Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Sergio Rajsbaum. Linear space bootstrap communication schemes. Theoretical Computer Science, 561:122-133, 2015. Google Scholar
  9. Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov, and Eric Ruppert. On the space complexity of set agreement? In 34th ACM Symposium on Principles of Distributed Computing, PODC '15, pages 271-280, 2015. Google Scholar
  10. Panagiota Fatourou, Faith Ellen Fich, and Eric Ruppert. Time-space tradeoffs for implementations of snapshots. In 38th ACM Symposium on Theory of Computing, STOC '06, pages 169-178, 2006. Google Scholar
  11. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-free synchronization: Double-ended queues as an example. In 23rd International Conference on Distributed Computing Systems, ICDCS '03, pages 522-529, 2003. Google Scholar
  12. Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for non-blocking implementations (preliminary version). In 15th ACM Symposium on Principles of Distributed Computing, PODC '96, pages 257-266, 1996. Google Scholar
  13. Leslie Lamport. On interprocess communication; part I and II. Distributed Computing, 1(2):77-101, 1986. Google Scholar
  14. F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30:264–286, 1930. Google Scholar
  15. Gadi Taubenfeld. Contention-sensitive data structures and algorithms. In 23rd International Conference on Distributed Computing, DISC'09, pages 157-171, 2009. Google Scholar
  16. Nayuta Yanagisawa. Wait-free solvability of colorless tasks in anonymous shared-memory model. In 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS '06, pages 415-429, 2016. Google Scholar
  17. Leqi Zhu. A tight space bound for consensus. In 48th ACM Symposium on Theory of Computing, STOC '16, pages 345-350, 2016. Google Scholar
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