An Efficient Practical Concurrent Wait-Free Unbounded Graph

Peri, Sathya and Reddy, Chandra Kiran and Sa, Muktikanta (2019) An Efficient Practical Concurrent Wait-Free Unbounded Graph. In: 21st IEEE International Conference on High Performance Computing and Communications, 17th IEEE International Conference on Smart City and 5th IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS, 10-12 August 2019, Zhangjiajie, China.

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

Abstract

In this paper, we propose an efficient concurrent wait-free algorithm to construct an unbounded directed graph for shared memory architecture. To the best of our knowledge that this is the first wait-free algorithm for an unbounded directed graph where insertion and deletion of vertices and/or edges can happen concurrently. To achieve wait-freedom in a dynamic setting, threads help each other to perform the desired tasks using operator descriptors by other threads. We also prove that all graph operations are wait-free and linearizable. We implemented our algorithms in C++ and tested its performance through several micro-benchmarks. Our experimental results show an average of 9x improvement over the global lock-based implementation.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Peri, SathyaUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Concurrent data-structure, Directed graph, Fast-path-slow-path, Lazy-list, Lock-free, Locks, Wait-free, Indexed in Scopus
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 28 Oct 2019 06:28
Last Modified: 28 Oct 2019 06:28
URI: http://raiith.iith.ac.in/id/eprint/6860
Publisher URL: http://doi.org/10.1109/HPCC/SmartCity/DSS.2019.003...
Related URLs:

    Actions (login required)

    View Item View Item
    Statistics for RAIITH ePrint 6860 Statistics for this ePrint Item