A Pragmatic Non-blocking Concurrent Directed Acyclic Graph

Peri, Sathya and Sa, Muktikanta and Singhal, Nandini (2019) A Pragmatic Non-blocking Concurrent Directed Acyclic Graph. In: 7th International Conference on Networked Systems, NETYS, 19-21 June 2019, Marrakech, Morocco.

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


In this paper, we have developed two non-blocking algorithms for maintaining acyclicity in a concurrent directed graph. The first algorithm is based on a wait-free reachability query and the second one on partial snapshot-based obstruction-free reachability query. Interestingly, we are able to achieve the acyclic property in a dynamic setting without (1) making use of helping descriptors by other threads, or (2) clean double collect mechanism. We present a proof to show that the graph remains acyclic at all times in the concurrent setting. We also prove that the acyclic graph data-structure operations are linearizable. We implement both the algorithms in C++ and test through several micro-benchmarks. Our experimental results illustrate an average of 7x improvement over the sequential and global-lock implementation.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Acyclic graph, Concurrent data structure, Linearizability, Lock-freedom, Indexed in Scopus
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 13 Dec 2019 06:25
Last Modified: 13 Dec 2019 06:25
URI: http://raiith.iith.ac.in/id/eprint/7148
Publisher URL: http://doi.org/10.1007/978-3-030-31277-0_22
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 7148 Statistics for this ePrint Item