A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries
Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. ACM International Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking, 168–177.
Download (ext.)
https://arxiv.org/abs/1809.00896
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Chatterjee, BapiISTA ;
Peri, Sathya;
Sa, Muktikanta;
Singhal, Nandini
Department
Abstract
Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.
Publishing Year
Date Published
2019-01-04
Proceedings Title
ACM International Conference Proceeding Series
Publisher
ACM
Page
168-177
Conference
ICDCN: Conference on Distributed Computing and Networking
Conference Location
Bangalore, India
Conference Date
2019-01-04 – 2019-01-07
ISBN
IST-REx-ID
Cite this
Chatterjee B, Peri S, Sa M, Singhal N. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In: ACM International Conference Proceeding Series. ACM; 2019:168-177. doi:10.1145/3288599.3288617
Chatterjee, B., Peri, S., Sa, M., & Singhal, N. (2019). A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. In ACM International Conference Proceeding Series (pp. 168–177). Bangalore, India: ACM. https://doi.org/10.1145/3288599.3288617
Chatterjee, Bapi, Sathya Peri, Muktikanta Sa, and Nandini Singhal. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” In ACM International Conference Proceeding Series, 168–77. ACM, 2019. https://doi.org/10.1145/3288599.3288617.
B. Chatterjee, S. Peri, M. Sa, and N. Singhal, “A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries,” in ACM International Conference Proceeding Series, Bangalore, India, 2019, pp. 168–177.
Chatterjee B, Peri S, Sa M, Singhal N. 2019. A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries. ACM International Conference Proceeding Series. ICDCN: Conference on Distributed Computing and Networking, 168–177.
Chatterjee, Bapi, et al. “A Simple and Practical Concurrent Non-Blocking Unbounded Graph with Linearizable Reachability Queries.” ACM International Conference Proceeding Series, ACM, 2019, pp. 168–77, doi:10.1145/3288599.3288617.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 1809.00896