Maintaining Acyclicity of Concurrent Graphs*

Peri, Sathya and Sa, M and Singhal, N (2016) Maintaining Acyclicity of Concurrent Graphs*. arXiv. pp. 1-23.

1611.03947.pdf - Accepted Version

Download (734kB) | Preview


In this paper, we consider the problem of preserving acyclicity in a directed graph (for shared memory architecture) that is concurrently being updated by threads adding/deleting vertices and edges. To the best of our knowledge, no previous paper has presented a con- current graph data structure. We implement the concurrent directed graph data-structure as a concurrent adjacency list representation. We extend the lazy list implementation of concurrent linked lists for maintaining concurrent adjacency lists. There exists a number of graph applications which require the acyclic invariant in a directed graph. One such example is Serialization Graph Testing Algorithm used in databases and transactional memory. We present two concurrent algorithms for maintaining acyclicity in a concurrent graph: (i) Based on obstruction-free snapshots (ii) Using wait-free reachability. We compare the performance of these algorithms against the coarse-grained locking strategy, commonly used technique for allowing concurrent updates. We present the speedup obtained by these algorithms over sequential execution. As a future direction, we plan to extend this data structure for other progress conditions.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Article
Uncontrolled Keywords: concurrent graphs; acyclicity; lazy list; directed graph; obstruction free; wait- free
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Nov 2016 11:31
Last Modified: 11 Sep 2017 05:09
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 2895 Statistics for this ePrint Item