Document Open Access Logo

Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds

Authors Bapi Chatterjee , Sathya Peri , Muktikanta Sa , Komma Manogna

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.20.pdf
  • Filesize: 2.28 MB
  • 25 pages

Document Identifiers

Author Details

Bapi Chatterjee
  • Indraprastha Institute of Information Technology Delhi, India
Sathya Peri
  • Indian Institute of Technology Hyderabad, India
Muktikanta Sa
  • Télécom SudParis - Institut Polytechnique de Paris, France
Komma Manogna
  • Indian Institute of Technology Hyderabad, India

Funding

This work was partially funded by National Supercomputing Mission, Govt. of India under the project "Concurrent and Distributed Programming primitives and algorithms for Temporal Graphs"(DST/NSM/R&D_Exascale/2021/16).

Cite As Get BibTex

Bapi Chatterjee, Sathya Peri, Muktikanta Sa, and Komma Manogna. Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 20:1-20:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.20

Abstract

Today’s graph-based analytics tasks in domains such as blockchains, social networks, biological networks, and several others demand real-time data updates at high speed. The real-time updates are efficiently ingested if the data structure naturally supports dynamic addition and removal of both edges and vertices. These dynamic updates are best facilitated by concurrency in the underlying data structure. Unfortunately, the existing dynamic graph frameworks broadly refurbish the static processing models using approaches such as versioning and incremental computation. Consequently, they carry their original design traits such as high memory footprint and batch processing that do not honor the real-time changes. At the same time, multi-core processors-a natural setting for concurrent data structures-are now commonplace, and the analytics tasks are moving closer to data sources over lightweight devices. Thus, exploring a fresh design approach for real-time graph analytics is significant.
This paper reports a novel concurrent graph data structure that provides breadth-first search, single-source shortest-path, and betweenness centrality with concurrent dynamic updates of both edges and vertices. We evaluate the proposed data structure theoretically - by an amortized analysis - and experimentally via a C++ implementation. The experimental results show that (a) our algorithm outperforms the current state-of-the-art by a throughput speed-up of up to three orders of magnitude in several cases, and (b) it offers up to 80x lighter memory-footprint compared to existing methods. The experiments include several counterparts: Stinger, Ligra and GraphOne. We prove that the presented concurrent algorithms are non-blocking and linearizable.

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrent algorithms
Keywords
  • concurrent data structure
  • linearizability
  • non-blocking
  • directed graph
  • breadth-first search
  • single-source shortest-path
  • betweenness centrality

Metrics

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

Related Versions

Supplementary Materials

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic Snapshots of Shared Memory. Journal of the ACM, 40(4):873-890, 1993. Google Scholar
  2. Yehuda Afek, Gideon Stupp, and Dan Touitou. Long Lived Adaptive Splitter and Applications. Distributed Comput., 15(2):67-86, 2002. Google Scholar
  3. H. Attiya and A. Fouren. Alg. Adapting to Point Contention. J. ACM, 50(4):444-468, 2003. Google Scholar
  4. Greg Barnes. A Method for Implementing Lock-free Shared-data Structures. In SPAA, pages 261-270, 1993. Google Scholar
  5. Omar Batarfi, Radwa El Shawi, Ayman G Fayoumi, Reza Nouri, Ahmed Barnawi, Sherif Sakr, et al. Large Scale Graph Processing Systems: Survey and an Experimental Evaluation. Cluster Computing, 18(3):1189-1213, 2015. Google Scholar
  6. Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In PPoPP, pages 329-342, 2014. Google Scholar
  7. A. Buluç, J. R. Gilbert, and V. B. Shah. Implementing Sparse Matrices for Graph Algorithms. In Graph Algorithms in the Language of Linear Algebra, volume 22, pages 287-313. SIAM, 2011. Google Scholar
  8. Hung Cao, Monica Wachowicz, and Sangwhan Cha. Developing an edge computing platform for real-time descriptive analytics. 2017 IEEE International Conference on Big Data (Big Data), pages 4546-4554, 2017. Google Scholar
  9. Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A recursive model for graph mining. In SDM, pages 442-446, 2004. Google Scholar
  10. Bapi Chatterjee, Nhan Nguyen, and Philippas Tsigas. Efficient Lock-free Binary Search Trees. In PODC, pages 322-331, 2014. Google Scholar
  11. Bapi Chatterjee, Sathya Peri, and Muktikanta Sa. Dynamic Graph Operations: A Consistent Non-blocking Approach. CoRR, abs/2003.01697, 2020. Google Scholar
  12. Bapi Chatterjee, Sathya Peri, Muktikanta Sa, and Nandini Singhal. A Simple and Practical Concurrent Non-blocking Unbounded Graph with Linearizable Reachability Queries. In ICDCN, pages 168-177, 2019. Google Scholar
  13. Bapi Chatterjee, Ivan Walulya, and Philippas Tsigas. Help-optimal and Language-portable Lock-free Concurrent Data Structures. In ICPP, pages 360-369, 2016. Google Scholar
  14. Raymond Cheng, Ji Hong, Aapo Kyrola, Youshan Miao, Xuetian Weng, Ming Wu, Fan Yang, Lidong Zhou, Feng Zhao, and Enhong Chen. Kineograph: taking the pulse of a fast-changing and connected world. In EuroSys, pages 85-98, 2012. Google Scholar
  15. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. Google Scholar
  16. Nhan Nguyen Dang and Philippas Tsigas. Progress guarantees when composing lock-free objects. In Euro-Par, pages 148-159, 2011. Google Scholar
  17. Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. Low-Latency Graph Streaming Using Compressed Purely-Functional Trees. In PLDI, pages 918-934, 2019. Google Scholar
  18. D. Ediger, R. McColl, J. Riedy, and D. A. Bader. STINGER: High Performance Data Structure for Streaming Graphs. In HPEC, 2012. Google Scholar
  19. Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In PODC, pages 131-140, 2010. Google Scholar
  20. Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, pages 17-30, 2012. Google Scholar
  21. Timothy L. Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In DISC, pages 300-314, 2001. Google Scholar
  22. Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit. A Lazy Concurrent List-Based Set Algorithm. Parallel Processing Letters, 17(4):411-424, 2007. Google Scholar
  23. Danny Hendler, Nir Shavit, and Lena Yerushalmi. A Scalable Lock-free Stack Algorithm. In SPAA, pages 206-215, 2004. Google Scholar
  24. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-Free Synchronization: Double-Ended Queues as an Example. In (ICDCS, pages 522-529, 2003. Google Scholar
  25. Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan K., 2008. Google Scholar
  26. Maurice Herlihy and Nir Shavit. On the Nature of Progress. In OPODIS, pages 313-328, 2011. Google Scholar
  27. Maurice Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. Google Scholar
  28. Shane V. Howley and Jeremy Jones. A Non-blocking Internal Binary Search Tree. In SPAA, pages 161-171, 2012. Google Scholar
  29. Wole Jaiyeoba and K. Skadron. Graphtinker: A high performance data structure for dynamic graph processing. IPDPS, pages 1030-1041, 2019. Google Scholar
  30. Nikolaos D. Kallimanis and Eleni Kanellou. Wait-Free Concurrent Graph Objects with Dynamic Traversals. In OPODIS, pages 1-27, 2015. Google Scholar
  31. Miray Kas, Kathleen M. Carley, and L. Richard Carley. Incremental Closeness Centrality for Dynamically Changing Social Networks. In ASONAM 2013, pages 1250-1258, 2013. Google Scholar
  32. Alex Kogan and Erez Petrank. Wait-Free Queues With Multiple Enqueuers and Dequeuers. In PPOPP, pages 223-234, 2011. Google Scholar
  33. Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and L. Paul Chew. Optimistic Parallelism Requires Abstractions. In PLDI, pages 211-222, 2007. Google Scholar
  34. P. Kumar and H. Huang. Graphone: A data store for real-time analytics on evolving graphs. In FAST, 2019. Google Scholar
  35. Edya Ladan-Mozes and Nir Shavit. An Optimistic Approach to Lock-free FIFO Queues. Distributed Computing, 20(5):323-341, 2008. Google Scholar
  36. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data, June 2014.
  37. Yujie Liu, Kunlong Zhang, and Michael Spear. Dynamic-sized Nonblocking Hash Tables. In PODC, pages 242-251, 2014. Google Scholar
  38. Maged M. Michael. High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. In SPAA, pages 73-82, 2002. Google Scholar
  39. Aravind Natarajan and Neeraj Mittal. Fast concurrent lock-free binary search trees. In PPoPP, pages 317-328, 2014. Google Scholar
  40. K A Obukhova, Iryna Zhuravska, and Volodymyr Burenko. Diagnostics of power consumption of a mobile device multi-core processor with detail of each core utilization. TCSET, pages 368-372, 2020. Google Scholar
  41. P. Pan, C. Li, and M. Guo. Congraplus: Towards efficient processing of concurrent graph queries on numa machines. IEEE TPDS, 30(9):1990-2002, 2019. Google Scholar
  42. Peitian Pan and Chao Li. Congra: Towards efficient processing of concurrent graph queries on shared-memory machines. In ICCD, pages 217-224, 2017. Google Scholar
  43. Arunmoezhi Ramachandran and Neeraj Mittal. A Fast Lock-Free Internal Binary Search Tree. In ICDCN, pages 37:1-37:10, 2015. Google Scholar
  44. Alberto G. Rossi, D. Blake, A. Timmermann, I. Tonks, and R. Wermers. Network centrality and delegated investment performance. Journal of Financial Economics, 128:183-206, 2018. Google Scholar
  45. Julian Shun and Guy E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In PPoPP, pages 135-146, 2013. Google Scholar
  46. Julian Shun, Laxman Dhulipala, and Guy E. Blelloch. Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+. In DCC, pages 403-412, 2015. Google Scholar
  47. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146-160, 1972. Google Scholar
  48. Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank. Wait-Free Linked-Lists. In OPODIS, pages 330-344, 2012. Google Scholar
  49. John D. Valois. Lock-Free Linked Lists Using Compare-and-Swap. In PODC, pages 214-222, 1995. Google Scholar
  50. Kunlong Zhang, Yujiao Zhao, Yajun Yang, Yujie Liu, and Michael F. Spear. Practical Non-blocking Unordered Lists. In DISC, pages 239-253, 2013. Google Scholar
  51. J. Zhao, Y. Zhang, X. Liao, L. He, B. He, H. Jin, H. Liu, and Y. Chen. Graphm: An efficient storage system for high throughput of concurrent graph processing. In SC, 2019. 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