10.1145/3288599.3288617
Chatterjee, Bapi
Bapi
Chatterjee
Peri, Sathya
Sathya
Peri
Sa, Muktikanta
Muktikanta
Sa
Singhal, Nandini
Nandini
Singhal
A simple and practical concurrent non-blocking unbounded graph with linearizable reachability queries
ACM
2019
2019-02-10T22:59:17Z
2019-11-14T08:43:19Z
conference
/record/5947
/record/5947.json
978-1-4503-6094-4
1809.00896
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.