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 Creators ORCiD Peri, Sathya UNSPECIFIED
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://raiithold.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

Statistics for this ePrint Item