2017/10/20 by Sathya Peri, Peri, Sathya, Muktikanta Sa +3
Computer Science · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1710.08296
17 pages, 5 figures
openalex publication_date 2017/10/20 · arxiv created 2017/10/31 · arxiv updated 2017/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose a generic concurrent directed graph (for shared memory architecture) that is concurrently being updated by threads adding/deleting vertices and edges. The graph is constructed by the composition of the well known concurrent list-based set data-structure from the literature. Our construction is generic, in the sense that it can be used to obtain various progress guarantees, depending on the granularity of the underlying concurrent set implementation - either blocking or non-blocking. We prove that the proposed construction is linearizable by identifying its linearization points. Finally, we compare the performance of all the variants of the concurrent graph data-structure along with its sequential implementation. We observe that our concurrent graph data-structure mimics the performance of the concurrent list based set.