Présentation « Dynamic Non-blocking Graph Algorithms » par Sathya Peri (IIT Hyderabad)

Titre : Dynamic Non-blocking Graph Algorithms

Résumé :
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.

Biographie :
Sathya Peri est Maître de Conférences au département CSE de l’IIT Hyderabad. Ses recherches portent sur les systèmes parallèles et distribués. Dans le domaine des systèmes parallèles, il explore les structures de données concurrentes, en particulier les graphes concurrents et dynamiques. Dans le cadre des systèmes distribués, il explore les problèmes de performance des blockchains dans le contexte de l’exécution des contrats intelligents dans les blockchains.