|
Lecture Announcement Venue: CMI Seminar Hall (Hybrid Mode) Date and Time: 2pm -- 3pm, Friday, 22nd April 2022 Dynamic Non-blocking Graph Algorithms Sathya Peri IIT Hyderabad. 22-04-22 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. At the end of the talk Dr. Sathya Peri will also make a short presentation about the Computer Science Department at IIT Hyderabad. Brief Biography Dr. Sathya Peri is currently an Associate Professor in CSE Department of IIT Hyderabad (IITH). His research interests broadly comprise of parallel and distributed systems. One of the areas he looks at is efficient ways to parallelize using Software Transactional Memory Systems (STMs) while also exploring lock-free & wait-free algorithms. In the context of distributed systems, his interest includes Blockchain and Peer-to-Peer Systems. He is currently working on improving the efficiency of Smart Contract Execution in Blockchains Systems.
|
