Talk by Sathya Peri (IIT Hyderabad) on dynamic graph algorithms

Title: Dynamic Non-blocking Graph Algorithms

Abstract:
Graph algorithms have several diverse applications, including social networks, communication networks, VLSI design, graphics etc. Many of these applications require dynamic modifications — addition and removal of vertices and/or edges — in the graph. Our team has recently developed algorithms for Concurrent Graphs which I will explain in this talk. In this work, we developed a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. In addition to these point operations, we then considered a set method which is the most significant component of the presented algorithm: reachability query in a concurrent graph which identifies if there is a path between two vertices in such a dynamic network. The solution to the reachability query in our algorithm is obstruction-free and thus impose minimal additional synchronization cost over other operations. We showed that each of the data structure operations are linearizable. We did some extensive evaluations on the C++ implementation of the algorithm through various micro-benchmarks. Our implementation results have also been very good. On an average, we perform around 5x times better than sequential graph implementation.

Bio:
Dr. Sathya Peri is currently an Associate Professor in CSE Department of IIT Hyderabad. His research interests include Parallel and Distributed Systems. In the area of Parallel Systems, he is exploring Concurrent Data-Structures, specifically concurrent & dynamic graphs. In the context of distributed systems, he is exploring performance issues in blockchains in the context of Smart Contract Execution in Blockchains.