| Title | : | Dynamic Non-blocking Graph Algorithms |
| Speaker | : | Sathya Peri (IIT Hyderabad) |
| Details | : | Fri, 28 Feb, 2020 12:00 PM @ AM Turing Hall |
| 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 is 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 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. |
