Document Open Access Logo

Nontrivial and Universal Helping for Wait-Free Queues and Stacks

Authors Hagit Attiya, Armando Castaneda, Danny Hendler

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.31.pdf
  • Filesize: 0.61 MB
  • 16 pages

Document Identifiers

Author Details

Hagit Attiya
Armando Castaneda
Danny Hendler

Cite As Get BibTex

Hagit Attiya, Armando Castaneda, and Danny Hendler. Nontrivial and Universal Helping for Wait-Free Queues and Stacks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.31

Abstract

This paper studies two approaches to formalize helping in wait-free implementations of shared objects. The first approach is based on operation valency, and it allows us to make the important distinction between trivial and nontrivial helping. We show that a wait-free implementation of a queue from common2 objects (e.g., Test&Set) requires nontrivial helping. In contrast, there is a wait-free implementation of a stack from Common2 objects with only trivial helping. This separation might shed light on the difficulty of implementing a queue from Common2 objects. 

The other approach formalizes the helping mechanism employed by Herlihy's universal wait-free construction and is based on having an operation by one process restrict the possible linearizations of operations by other processes. We show that objects possessing such universal helping can be used to solve consensus.

Subject Classification

Keywords
  • helping
  • wait-free
  • nonblocking
  • queues
  • stacks
  • common2

Metrics

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

References

  1. Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. Distributed Computing, 20(4):239-252, 2007. Google Scholar
  2. Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC'93, pages 159-170, 1993. Google Scholar
  3. Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC'15, pages 241-250, 2015. Google Scholar
  4. Matei David. A single-enqueuer wait-free queue implementation. In Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, pages 132-143, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30186-8_10.
  5. Matei David. Wait-free linearizable queue implementation. Master’s thesis, Department of Computer Science, University of Toronto, 2004. Google Scholar
  6. Matei David, Alex Brodsky, and Faith Ellen Fich. Restricted stack implementations. In Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings, pages 137-151, 2005. URL: http://dx.doi.org/10.1007/11561927_12.
  7. Oksana Denysyuk and Philipp Woelfel. Wait-freedom is harder than lock-freedom under strong linearizability. In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 60-74, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_5.
  8. David Eisenstat. A two-enqueuer queue. CoRR, abs/0805.0444, 2008. URL: http://arxiv.org/abs/0805.0444.
  9. Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC'11, pages 373-382, 2011. Google Scholar
  10. Maryam Helmi, Lisa Higham, and Philipp Woelfel. Strongly linearizable implementations: possibilities and impossibilities. In ACM Symposium on Principles of Distributed Computing, PODC'12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 385-394, 2012. URL: http://dx.doi.org/10.1145/2332432.2332508.
  11. Danny Hendler and Nir Shavit. Operation-valency and the cost of coordination. In Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC'03, pages 84-91, 2003. Google Scholar
  12. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991. Google Scholar
  13. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, July 1990. Google Scholar
  14. Zongpeng Li. Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Master’s thesis, Department of Computer Science, University of Toronto, 2001. 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