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)

Abstract

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: