| Title | : | A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees |
| Speaker | : | Gopal Pandurangan (IITM) |
| Details | : | Tue, 12 Mar, 2019 3:00 PM @ A M Turing Hall |
| Abstract: | : | The distributed minimum spanning tree (MST) problem is one of the central problems in distributed computing.
In this talk, we present a randomized (Las Vegas) distributed algorithm that constructs a MST in
weighted networks with optimal (up to polylogarithmic factors) time and message complexity.
This algorithm runs in tilde{O}(D + sqrt{n}) time and exchanges tilde{O}(m) messages (both with high probability), where
n is the number of nodes of the network, D is the diameter, and m is the number of edges.This is the first distributed MST algorithm that is simultaneously optimal with respect to both time and message complexities.
This work is joint with Peter Robinson and Michele Scquizzato and appeared in STOC 2017. Brief Bio of the Speaker: Gopal Pandurangan is a Professor in the Department of Computer Science at the University of Houston and a VAJRA visiting professor at the Indian Institute of Technology, Madras. He received his Ph.D. from Brown University, Masters from SUNY Albany, and B.Tech. from IIT Madras (all in Computer Science). He has held faculty and visiting positions at Nanyang Technological University (Division of Mathematical Sciences) in Singapore, Brown University, Purdue University, and Rutgers University. His research interests are in theory and algorithms, distributed computing, networks, large-scale data, and computational biology. He has published over 100 refereed papers in these areas. His work has appeared in JACM, SICOMP, ACM TALG, STOC, FOCS, SODA, PODC, SPAA, and RECOMB. His research has been supported by research grants from the US National Science Foundation, US-Israeli Binational Science Foundation, and the Singapore Ministry of Education. |
