Peri, Sathya and Sa, M and Singhal, N
(2016)
Maintaining Acyclicity of Concurrent Graphs*.
arXiv.
pp. 1-23.
Abstract
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.
Actions (login required)
 |
View Item |
Altmetric
Altmetric