Document Open Access Logo

Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds

Authors Bapi Chatterjee , Sathya Peri , Muktikanta Sa

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.52.pdf
  • Filesize: 0.75 MB
  • 4 pages

Document Identifiers

Author Details

Bapi Chatterjee
  • Institute of Science and Technology, Klosterneuburg, Austria
Sathya Peri
  • Indian Institute of Technology, Hyderabad, India
Muktikanta Sa
  • Télécom SudParis - Institut Polytechnique de Paris, France

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 AsGet BibTex

Bapi Chatterjee, Sathya Peri, and Muktikanta Sa. Brief Announcement: Non-Blocking Dynamic Unbounded Graphs with Worst-Case Amortized Bounds. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 52:1-52:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.52

Abstract

This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.

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

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. Parwat Singh Anjana, Sweta Kumari, Sathya Peri, Sachin Rathor, and Archit Somani. An Efficient Framework for Optimistic Concurrent Execution of Smart Contracts. In (PDP) 2019, pages 83-92, 2019. Google Scholar
  4. Hagit Attiya and Arie Fouren. Algorithms Adapting to Point Contention. J. ACM, 50(4):444-468, 2003. Google Scholar
  5. Sumit Bhatia, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. A Persistent Homology Perspective to the Link Prediction Problem. In Complex Networks, page (to appear), 2019. Google Scholar
  6. Salvatore Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Alessandro Provetti. Crawling Facebook for Social Network Analysis Purposes. In (WIMS), page 52, 2011. Google Scholar
  7. Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A recursive model for graph mining. In SDM, pages 442-446, 2004. Google Scholar
  8. Bapi Chatterjee, Sathya Peri, and Muktikanta Sa. Dynamic Graph Operations: A Consistent Non-blocking Approach. CoRR, abs/2003.01697, 2020. Google Scholar
  9. 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
  10. Antonio del Sol, Hirotomo Fujihashi, and Paul O'Meara. Topology of Small-world Networks of Protein–Protein Complex Structures. Bioinformatics, 21(8):1311-1315, 2005. Google Scholar
  11. Laxman Dhulipala, Guy E Blelloch, and Julian Shun. Low-latency graph streaming using compressed purely-functional trees. In 40th PLDI, pages 918-934, 2019. Google Scholar
  12. D. Ediger, R. McColl, J. Riedy, and D. A. Bader. STINGER: High Performance Data Structure for Streaming Graphs. In HPEC, 2012. Google Scholar
  13. 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
  14. Anand Padmanabha Iyer, Li Erran Li, Tathagata Das, and Ion Stoica. Time-evolving Graph Processing at Scale. In GRADES, page 5, 2016. Google Scholar
  15. Wole Jaiyeoba and K. Skadron. Graphtinker: A high performance data structure for dynamic graph processing. IPDPS, pages 1030-1041, 2019. Google Scholar
  16. P. Kumar and H. Huang. Graphone: A data store for real-time analytics on evolving graphs. In FAST, 2019. Google Scholar
  17. Julian Shun and Guy E. Blelloch. Ligra: a Lightweight Graph Processing Framework for Shared Memory. In PPoPP, pages 135-146, 2013. Google Scholar
  18. Keval Vora, R. Gupta, and Guoqing Xu. Kickstarter: Fast and accurate computations on streaming graphs via trimmed approximations. ASPLOS, 2017. 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 Imprint Privacy Contact