Document Open Access Logo

Wait-Free Concurrent Graph Objects with Dynamic Traversals

Authors Nikolaos D. Kallimanis, Eleni Kanellou

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.27.pdf
  • Filesize: 0.51 MB
  • 17 pages

Document Identifiers

Author Details

Nikolaos D. Kallimanis
Eleni Kanellou

Cite As Get BibTex

Nikolaos D. Kallimanis and Eleni Kanellou. Wait-Free Concurrent Graph Objects with Dynamic Traversals. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.27

Abstract

Graphs are versatile data structures that allow the implementation of a variety of applications, such as computer-aided design and manufacturing, video gaming, or scientific simulations. However, although data structures such as queues, stacks, and trees have been widely studied and implemented in the concurrent context, multi-process applications that rely on graphs still largely use a sequential implementation where accesses are synchronized through the use of global locks or partitioning, thus imposing serious performance bottlenecks. In this paper we introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. We further present Dense, a concurrent graph implementation that aims at mitigating the two aforementioned implementation drawbacks. Dense achieves wait-freedom by relying on helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph.

Subject Classification

Keywords
  • graph
  • shared memory
  • concurrent data structure
  • snapshot

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: http://dx.doi.org/10.1145/153724.153741.
  2. Marcos Kawazoe Aguilera, Wojciech M. Golab, and Mehul A. Shah. A practical scalable distributed b-tree. PVLDB, 1(1):598-609, 2008. Google Scholar
  3. Zeyad Abd Algfoor, Mohd Shahrizal Sunar, and Hoshang Kolivand. A comprehensive study on pathfinding techniques for robotics and video games. International Journal of Computer Games Technology, 2015. Google Scholar
  4. Hagit Attiya, Rachid Guerraoui, and Eric Ruppert. Partial snapshot objects. In Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 336-343, NY, USA, 2008. ACM. Google Scholar
  5. Gal Bar-Nissan, Danny Hendler, and Adi Suissa. A dynamic elimination-combining stack algorithm. CoRR, abs/1106.6304, 2011. Google Scholar
  6. Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 329-342, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2555243.2555267.
  7. Vadim Bulitko, Yngvi Bjornsson, Nathan R. Sturtevant, and Ramon Lawrence. Real-time heuristic search for pathfinding in video games. In Artificial Intelligence for Computer Games, pages 1-30. Springer New York, 2011. URL: http://dx.doi.org/10.1007/978-1-4419-8188-2_1.
  8. Victor Bushkov, Rachid Guerraoui, and Michal Kapalka. On the liveness of transactional memory. In Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 9-18, NY, USA, 2012. ACM. Google Scholar
  9. Joseph Carsten, Arturo Rankin, Dave Ferguson, and Anthony Stentz. Global planning on the mars exploration rovers: Software integration and surface testing. J. Field Robot., 26(4):337-357, April 2009. URL: http://dx.doi.org/10.1002/rob.v26:4.
  10. Bapi Chatterjee, Nhan Nguyen, and Philippas Tsigas. Efficient lock-free binary search trees. In Proceedings of the 33rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 322-331, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2611462.2611500.
  11. Guojing Cong, Sreedhar B. Kodali, Sriram Krishnamoorthy, Doug Lea, Vijay A. Saraswat, and Tong Wen. Solving large, irregular graph problems using adaptive work-stealing. In 37th International Conference on Parallel Processing (ICPP), pages 536-545, 2008. Google Scholar
  12. Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 131-140, NY, USA, 2010. ACM. URL: http://dx.doi.org/10.1145/1835698.1835736.
  13. Panagiota Fatourou, Mykhailo Iaremko, Eleni Kanellou, and Eleftherios Kosmas. Algorithmic techniques in stm design. In Transactional Memory. Foundations, Algorithms, Tools, and Applications, volume 8913, pages 101-126. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-14720-8_5.
  14. Panagiota Fatourou and Nikolaos D. Kallimanis. Highly-efficient wait-free synchronization. Theory of Computing Systems, pages 1-46, 2013. URL: http://dx.doi.org/10.1007/s00224-013-9491-y.
  15. Timothy L. Harris. A pragmatic implementation of non-blocking linked-lists. In Proceedings of the 15th International Conference on Distributed Computing (DISC), pages 300-314, London, UK, 2001. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=645958.676105.
  16. Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. Scalable flat-combining based synchronous queues. In Distributed Computing, volume 6343, pages 79-93. Springer, 2010. Google Scholar
  17. Danny Hendler, Nir Shavit, and Lena Yerushalmi. A scalable lock-free stack algorithm. In Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 206-215. ACM, 2004. Google Scholar
  18. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. URL: http://dx.doi.org/10.1145/114005.102808.
  19. Maurice Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 15(5):745-770, 1993. Google Scholar
  20. Maurice Herlihy and J. Eliot B. Moss. Transactional memory: Architectural support for lock-free data structures. SIGARCH Comput. Archit. News, 21(2):289-300, May 1993. Google Scholar
  21. Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. Google Scholar
  22. Damien Imbs and Michel Raynal. Help when needed, but no more: Efficient read/write partial snapshot. In Distributed Computing, volume 5805, pages 142-156. Springer Berlin Heidelberg, 2009. Google Scholar
  23. Prasad Jayanti and Srdjan Petrovic. Logarithmic-time single deleter, multiple inserter wait-free queues and stacks. In Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 408-419. Springer-Verlag, 2005. URL: http://dx.doi.org/10.1007/11590156_33.
  24. Frank M. Johannes. Partitioning of vlsi circuits and systems. In Proceedings of the 33rd Annual Design Automation Conference, DAC'96, pages 83-87, NY, USA, 1996. ACM. Google Scholar
  25. Alex Kogan and Erez Petrank. Wait-free queues with multiple enqueuers and dequeuers. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 223-234, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1941553.1941585.
  26. Alex Kogan and Erez Petrank. A methodology for creating fast wait-free data structures. SIGPLAN Not., 47(8):141-150, February 2012. URL: http://dx.doi.org/10.1145/2370036.2145835.
  27. Yu-Kwong Kwok and Ishfaq Ahmad. Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distrib. Comput., 59(3):381-422, December 1999. URL: http://dx.doi.org/10.1006/jpdc.1999.1578.
  28. Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 267-275, NY, USA, 1996. ACM. URL: http://dx.doi.org/10.1145/248052.248106.
  29. Donald Nguyen and Keshav Pingali. Synthesizing concurrent schedulers for irregular algorithms. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 333-344, 2011. URL: http://dx.doi.org/10.1145/1950365.1950404.
  30. Yiannis Nikolakopoulos, Anders Gidenstam, Marina Papatriantafilou, and Philippas Tsigas. A consistency framework for iteration operations in concurrent data structures. In 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, May 25-29, 2015, pages 239-248, 2015. URL: http://dx.doi.org/10.1109/IPDPS.2015.84.
  31. Erez Petrank and Shahar Timnat. Lock-free data-structure iterators. In Distributed Computing, volume 8205, pages 224-238. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-41527-2_16.
  32. Aleksandar Prokopec, Nathan G. Bronson, Phil Bagwell, and Martin Odersky. Concurrent tries with efficient non-blocking snapshots. SIGPLAN Not., 47(8):151-160, Feb 2012. URL: http://dx.doi.org/10.1145/2370036.2145836.
  33. Dimitrios Prountzos, Roman Manevich, and Keshav Pingali. Elixir: A system for synthesizing concurrent graph programs. SIGPLAN Not., 47(10):375-394, October 2012. URL: http://dx.doi.org/10.1145/2398857.2384644.
  34. William N. Scherer III, Doug Lea, and Michael L. Scott. Scalable synchronous queues. In Proceedings of the 11th ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), NY, USA, 2006. ACM. Google Scholar
  35. Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 204-213, NY, USA, 1995. ACM. Google Scholar
  36. Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561, November 2011. URL: http://dl.acm.org/citation.cfm?id=1953048.2078187.
  37. S. Taylor, J.R. Watts, M.A. Rieffel, and M.E. Palmer. The concurrent graph: basic technology for irregular problems. Parallel Distributed Technology: Systems Applications, IEEE, 4(2):15-25, Summer 1996. URL: http://dx.doi.org/10.1109/88.494601.
  38. Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank. Wait-free linked-lists. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 309-310, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2145816.2145869.
  39. Chung Yung, Jheng-Jyun Syu, and Shiang-Yu Yang. A graph-based algorithm of mostly incremental garbage collection for active object systems. In International Computer Symposium (ICS), pages 988-996, 2010. URL: http://dx.doi.org/10.1109/COMPSYM.2010.5685367.
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