Document Open Access Logo

Brief Announcement: Persistent Software Combining

Authors Panagiota Fatourou, Nikolaos D. Kallimanis, Eleftherios Kosmas

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.56.pdf
  • Filesize: 474 kB
  • 4 pages

Document Identifiers

Author Details

Panagiota Fatourou
  • Foundation for Research and Technology - Hellas, Institute of Computer Science, Heraklion, Greece
  • University of Crete, Department of Computer Science, Heraklion, Greece
Nikolaos D. Kallimanis
  • Foundation for Research and Technology - Hellas, Institute of Computer Science, Heraklion, Greece
Eleftherios Kosmas
  • University of Crete, Department of Computer Science, Heraklion, Greece

Funding

Panagiota Fatourou: Supported by the EU Horizon 2020, Marie Sklodowska-Curie project with GA No 101031688. Eleftherios Kosmas: Co-financed by Greece and the European Union (European Social Fund- ESF) through the Operational Programme «Human Resources Development, Education and Lifelong Learning» in the context of the project “Reinforcement of Postdoctoral Researchers - 2nd Cycle” (MIS-5033021), implemented by the State Scholarships Foundation (IKY).

Cite As Get BibTex

Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleftherios Kosmas. Brief Announcement: Persistent Software Combining. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.56

Abstract

We study the performance power of software combining in designing recoverable algorithms and data structures. We present two recoverable synchronization protocols, one blocking and another wait-free, which illustrate how to use software combining to achieve both low persistence and synchronization cost. Our experiments show that these protocols outperform by far state-of-the-art recoverable universal constructions and transactional memory systems. We built recoverable queues and stacks, based on these protocols, that exhibit much better performance than previous such implementations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • Persistent objects
  • recoverable algorithms
  • durability
  • synchronization protocols
  • software combining
  • universal constructions
  • wait-freedom
  • stacks
  • queues

Metrics

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

Related Versions

References

  1. N. Ben-David, G. E. Blelloch, M. Friedman, and Y. Wei. Delay-free concurrency on faulty persistent memory. In ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 253-264, 2019. Google Scholar
  2. A. Correia, P. Felber, and P. Ramalhete. The Code for RedoDB. URL: https://github.com/pramalhe/RedoDB.
  3. A. Correia, P. Felber, and P. Ramalhete. Romulus: Efficient algorithms for persistent transactional memory. In Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 271-282, 2018. Google Scholar
  4. A. Correia, P. Felber, and P. Ramalhete. Persistent memory and the rise of universal constructions. In European Conference on Computer Systems (EuroSys), 2020. Google Scholar
  5. T. S. Craig. Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02, Dept. of Computer Science, University of Washington, 1993. Google Scholar
  6. D. Dice, V. J. Marathe, and N. Shavit. Lock cohorting: a general technique for designing numa locks. ACM SIGPLAN Notices, 47(8):247-256, 2012. Google Scholar
  7. P. Fatourou and N. D. Kallimanis. The RedBlue Adaptive Universal Constructions. In International Symp. on Distributed Computing (DISC), pages 127-141, 2009. Google Scholar
  8. P. Fatourou and N. D. Kallimanis. A highly-efficient wait-free universal construction. In ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 325-334, 2011. Google Scholar
  9. P. Fatourou and N. D. Kallimanis. Revisiting the combining synchronization technique. In ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 257-626, 2012. Google Scholar
  10. P. Fatourou and N. D. Kallimanis. Highly-efficient wait-free synchronization. Theory of Computing Systems, 55(3):475-520, 2014. Google Scholar
  11. P. Fatourou and N. D. Kallimanis. Lock oscillation: Boosting the performance of concurrent data structures. In Conf. on Principles of Distributed Systems (OPODIS), 2018. Google Scholar
  12. P. Fatourou and N. D. Kallimanis. The RedBlue family of universal constructions. Distributed Computing, 33:485-513, 2020. Google Scholar
  13. P. Fatourou, N. D. Kallimanis, and E. Kanellou. An efficient universal construction for large objects. In Conf. on Principles of Distributed Systems (OPODIS), pages 18:1-18:15, 2018. Google Scholar
  14. P. Fatourou, N. D. Kallimanis, and E. Kosmas. Persistent software combining. CoRR, abs/2107.03492, 2021. URL: http://arxiv.org/abs/2107.03492.
  15. M. Friedman, M. Herlihy, V. Marathe, and E. Petrank. A persistent lock-free queue for non-volatile memory. ACM SIGPLAN Notices, 53(1):28-40, 2018. Google Scholar
  16. D. Hendler, I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In ACM Symp. on Parallelism in algorithms and architectures (SPAA), pages 355-364, 2010. Google Scholar
  17. M. Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems, 15(5):745-770, 1993. Google Scholar
  18. J. Izraelevitz, H. Mendes, and M. L. Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In International Symp. on Distributed Computing (DISC), pages 313-327, 2016. Google Scholar
  19. P. S. Magnusson, A. Landin, and E. Hagersten. Queue Locks on Cache Coherent Multiprocessors. In International Parallel Processing Symposium, pages 165-171, 1994. Google Scholar
  20. J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. on Computer Systems (TOCS), 9(1):21-65, 1991. Google Scholar
  21. Y. Oyama, K. Taura, and A. Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently. In Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA), pages 182-204, 1999. Google Scholar
  22. PMDK. The persistent memory development kit. URL: https://github.com/pramalhe/RedoDB.
  23. P. Ramalhete, A. Correia, P. Felber, and N. Cohen. Onefile: A wait-free persistent transactional memory. In IEEE Conf. on Dependable Systems and Networks (DSN), pages 151-163, 2019. Google Scholar
  24. M. Rusanovsky, O. Ben-Baruch, D. Hendler, and P. Ramalhete. A flat-combining-based persistent stack for non-volatile memory. CoRR, abs/2012.12868, 2020 (version submited at 23 December, 2020). URL: http://arxiv.org/abs/2012.12868.
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