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

Chatterjee, Bapi and Peri, Sathya and Sa, Muktikanta and Singhal, Nandini (2019) A simple and practical concurrent non-blocking unbounded graph with linearizable reachability qeries. In: 20th International Conference on Distributed Computing and Networking, 4-7 January 2019, Bangalore, India.

Full text not available from this repository. (Request a copy)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 16 Jan 2019 04:02
Last Modified: 16 Jan 2019 04:02
URI: http://raiith.iith.ac.in/id/eprint/4717
Publisher URL: http://doi.org/10.1145/3288599.3288617
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4717 Statistics for this ePrint Item