| Title | : | Message Complexity of Distributed Algorithms |
| Speaker | : | Dr. Shreyas Pai (Postdoctoral researcher in the Theory group at Aalto University) |
| Details | : | Wed, 15 Mar, 2023 3:00 PM @ SSB 223 |
| Abstract: | : | In this talk we will look at the communication cost (or message complexity) of fundamental problems in the distributed CONGEST model. We will address the following question in this talk: can we solve problems using sublinear, i.e., $o(m)$ communication, and if so under what conditions? In a classical result, Awerbuch, Goldreich, Peleg, and Vainish [JACM 1990] showed that fundamental global problems such as broadcast and spanning tree construction require at least $Omega(m)$ messages in the KT-1 CONGEST model (i.e., CONGEST model in which nodes have initial knowledge of the neighbors' IDs) when algorithms are restricted to be comparison-based (i.e., algorithms in which node IDs can only be compared). Thirty five years after this result, King, Kutten, and Thorup [PODC 2015] showed that one can solve the above problems using $tilde{O}(n)$ messages ($n$ is the number of nodes in the graph) in $tilde{O}(n)$ rounds in the KT-1 CONGEST model if non-comparison-based algorithms are permitted. An important implication of this result is that one can use the synchronous nature of the KT-1 CONGEST model, using silence to convey information, and solve any graph problem using non-comparison-based algorithms with $tilde{O}(n)$ messages, but this takes an exponential number of rounds. In contrast, much less is known about the message complexity of local symmetry breaking problems such as vertex coloring and maximal independent set. We will look at the following results in this talk: - Lower bound: In the KT-1 CONGEST model, any comparison-based algorithm, even a randomized Monte-Carlo algorithm with constant success probability, requires $Omega(n^2)$ messages in the worst case to solve $(Delta+1)$-coloring, regardless of the number of rounds. - Upper bound: In the KT-1 CONGEST model, there is a randomized non-comparison-based $(Delta+1)$-coloring algorithm that uses $tilde{O}(n^{1.5})$ messages, while running in $tilde{O}(D+sqrt{n})$ rounds, where $D$ is the graph diameter. |
