Document Open Access Logo

Relaxed Queues and Stacks from Read/Write Operations

Authors Armando Castañeda, Sergio Rajsbaum, Michel Raynal

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.13.pdf
  • Filesize: 0.67 MB
  • 19 pages

Document Identifiers

Author Details

Armando Castañeda
  • Instituto de Matemáticas, UNAM, Mexico City, Mexico
Sergio Rajsbaum
  • Instituto de Matemáticas, UNAM, Mexico City, Mexico
Michel Raynal
  • Institut Universitaire de France, IRISA-Université de Rennes, France
  • Polytechnic University of Hong Kong, Hong Kong

Funding

  • Castañeda, Armando: Supported by UNAM-PAPIIT project IN108720.
  • Rajsbaum, Sergio: Supported by UNAM-PAPIIT project IN106520.
  • Raynal, Michel: Supported by French ANR project DESCARTES (16-CE40-0023-03).

Cite As Get BibTex

Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Relaxed Queues and Stacks from Read/Write Operations. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.13

Abstract

Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Computing methodologies → Distributed algorithms
  • Computing methodologies → Concurrent algorithms
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Asynchrony
  • Correctness condition
  • Linearizability
  • Nonblocking
  • Process crash
  • Relaxed data type
  • Set-linearizability
  • Wait-freedom
  • Work-stealing

Metrics

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

Related Versions

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: https://doi.org/10.1145/153724.153741.
  2. Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. Distributed Comput., 20(4):239-252, 2007. URL: https://doi.org/10.1007/s00446-007-0023-3.
  3. Yehuda Afek, Guy Korland, and Eitan Yanovsky. Quasi-linearizability: Relaxed consistency for improved concurrency. In Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, pages 395-410, 2010. URL: https://doi.org/10.1007/978-3-642-17653-1_29.
  4. Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects (extended abstract). In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing, Ithaca, New York, USA, August 15-18, 1993, pages 159-170, 1993. URL: https://doi.org/10.1145/164051.164071.
  5. Dan Alistarh, Trevor Brown, Justin Kopinsky, Jerry Zheng Li, and Giorgi Nadiradze. Distributionally linearizable data structures. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pages 133-142, 2018. URL: https://doi.org/10.1145/3210377.3210411.
  6. Dan Alistarh, Justin Kopinsky, Jerry Li, and Nir Shavit. The spraylist: a scalable relaxed priority queue. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015, San Francisco, CA, USA, February 7-11, 2015, pages 11-20, 2015. URL: https://doi.org/10.1145/2688500.2688523.
  7. James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. J. ACM, 59(1):2:1-2:24, 2012. URL: https://doi.org/10.1145/2108242.2108244.
  8. 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.
  9. 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: https://doi.org/10.1145/79147.79158.
  10. Hagit Attiya, Armando Castañeda, and Danny Hendler. Nontrivial and universal helping for wait-free queues and stacks. J. Parallel Distributed Comput., 121:1-14, 2018. URL: https://doi.org/10.1016/j.jpdc.2018.06.004.
  11. Hagit Attiya, Rachid Guerraoui, Danny Hendler, and Petr Kuznetsov. The complexity of obstruction-free implementations. J. ACM, 56(4):24:1-24:33, 2009. URL: https://doi.org/10.1145/1538902.1538908.
  12. Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin T. Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 487-498, 2011. URL: https://doi.org/10.1145/1926385.1926442.
  13. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. The renaming problem in shared memory systems: An introduction. Comput. Sci. Rev., 5(3):229-251, 2011. URL: https://doi.org/10.1016/j.cosrev.2011.04.001.
  14. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Unifying concurrent objects and distributed tasks: Interval-linearizability. J. ACM, 65(6):45:1-45:42, 2018. URL: https://doi.org/10.1145/3266457.
  15. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. What can be done with consensus number one: Relaxed queues and stacks. CoRR, abs/2005.05427, 2020. URL: http://arxiv.org/abs/2005.05427.
  16. 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: https://doi.org/10.1007/978-3-540-30186-8_10.
  17. 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: https://doi.org/10.1007/11561927_12.
  18. David Eisenstat. A two-enqueuer queue. CoRR, abs/0805.0444, 2008. URL: http://arxiv.org/abs/0805.0444.
  19. Faith Ellen, Danny Hendler, and Nir Shavit. On the inherent sequentiality of concurrent objects. SIAM J. Comput., 41(3):519-536, 2012. URL: https://doi.org/10.1137/08072646X.
  20. Andreas Haas, Thomas A. Henzinger, Andreas Holzer, Christoph M. Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. Local linearizability for concurrent container-type data structures. In 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Québec City, Canada, pages 6:1-6:15, 2016. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2016.6.
  21. Andreas Haas, Michael Lippautz, Thomas A. Henzinger, Hannes Payer, Ana Sokolova, Christoph M. Kirsch, and Ali Sezgin. Distributed queues in shared memory: multicore performance and scalability through quantitative relaxation. In Computing Frontiers Conference, CF'13, Ischia, Italy, May 14 - 16, 2013, pages 17:1-17:9, 2013. URL: https://doi.org/10.1145/2482767.2482789.
  22. Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, and Ana Sokolova. Quantitative relaxation of concurrent data structures. In The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '13, Rome, Italy - January 23 - 25, 2013, pages 317-328, 2013. URL: https://doi.org/10.1145/2429069.2429109.
  23. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991. URL: https://doi.org/10.1145/114005.102808.
  24. Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan Kaufmann, 2008. Google Scholar
  25. Maurice Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. URL: https://doi.org/10.1145/78969.78972.
  26. Damien Imbs and Michel Raynal. Help when needed, but no more: Efficient read/write partial snapshot. J. Parallel Distributed Comput., 72(1):1-12, 2012. URL: https://doi.org/10.1016/j.jpdc.2011.08.005.
  27. Christoph M. Kirsch, Michael Lippautz, and Hannes Payer. Fast and scalable, lock-free k-fifo queues. In Parallel Computing Technologies - 12th International Conference, PaCT 2013, St. Petersburg, Russia, September 30 - October 4, 2013. Proceedings, pages 208-223, 2013. URL: https://doi.org/10.1007/978-3-642-39958-9_18.
  28. Christoph M. Kirsch, Hannes Payer, Harald Röck, and Ana Sokolova. Performance, scalability, and semantics of concurrent FIFO queues. In Algorithms and Architectures for Parallel Processing - 12th International Conference, ICA3PP 2012, Fukuoka, Japan, September 4-7, 2012, Proceedings, Part I, pages 273-287, 2012. URL: https://doi.org/10.1007/978-3-642-33078-0_20.
  29. Zongpeng Li. Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Master’s thesis, University of Toronto, 2001. URL: http://hdl.handle.net/1807/16583.
  30. Maged M. Michael, Martin T. Vechev, and Vijay A. Saraswat. Idempotent work stealing. In Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2009, Raleigh, NC, USA, February 14-18, 2009, pages 45-54, 2009. URL: https://doi.org/10.1145/1504176.1504186.
  31. Mark Moir and James H. Anderson. Wait-free algorithms for fast, long-lived renaming. Sci. Comput. Program., 25(1):1-39, 1995. URL: https://doi.org/10.1016/0167-6423(95)00009-H.
  32. Mark Moir and Nir Shavit. Concurrent data structures. In Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004. URL: https://doi.org/10.1201/9781420035179.ch47.
  33. Gil Neiger. Set-linearizability. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, California, USA, August 14-17, 1994, page 396, 1994. URL: https://doi.org/10.1145/197917.198176.
  34. Donald Nguyen, Andrew Lenharth, and Keshav Pingali. A lightweight infrastructure for graph analytics. In ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP '13, Farmington, PA, USA, November 3-6, 2013, pages 456-471, 2013. URL: https://doi.org/10.1145/2517349.2522739.
  35. Hannes Payer, Harald Röck, Christoph M. Kirsch, and Ana Sokolova. Scalability versus semantics of concurrent FIFO queues. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011, pages 331-332, 2011. URL: https://doi.org/10.1145/1993806.1993869.
  36. Michel Raynal. Concurrent Programming - Algorithms, Principles, and Foundations. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-32027-9.
  37. Hamza Rihani, Peter Sanders, and Roman Dementiev. Brief announcement: Multiqueues: Simple relaxed concurrent priority queues. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 80-82, 2015. URL: https://doi.org/10.1145/2755573.2755616.
  38. Nir Shavit. Data structures in the multicore age. Commun. ACM, 54(3):76-84, 2011. URL: https://doi.org/10.1145/1897852.1897873.
  39. Nir Shavit and Gadi Taubenfeld. The computability of relaxed data structures: queues and stacks as examples. Distributed Comput., 29(5):395-407, 2016. URL: https://doi.org/10.1007/s00446-016-0272-0.
  40. Edward Talmage and Jennifer L. Welch. Relaxed data types as consistency conditions. Algorithms, 11(5):61, 2018. URL: https://doi.org/10.3390/a11050061.
  41. Gadi Taubenfeld. Synchronization algorithms and concurrent programming. Prentice Hall, 2006. Google Scholar
  42. Tingzhe Zhou, Maged M. Michael, and Michael F. Spear. A practical, scalable, relaxed priority queue. In Proceedings of the 48th International Conference on Parallel Processing, ICPP 2019, Kyoto, Japan, August 05-08, 2019, pages 57:1-57:10, 2019. URL: https://doi.org/10.1145/3337821.3337911.
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