A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries

B. Chatterjee, S. Peri, M. Sa, N. Singhal, in:, ACM International Conference Proceeding Series, ACM, 2019, pp. 168–177.


Conference Paper | Published | English
Author
; ; ;
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
Page
168-177
Conference
ICDCN: Conference on Distributed Computing and Networking
Conference Location
Bangalore, India
Conference Date
2019-01-04 – 2019-01-07
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.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1809.00896

Search this title in

Google Scholar
ISBN Search