Round- and Message-Optimal Distributed Graph Algorithms

Understand

Distributed graph algorithms that separately optimize for either the number of rounds used or the total number of messages sent have been studied extensively.

• However, algorithms simultaneously efficient with respect to both measures have been elusive.
• For example, only very recently was it shown that for Minimum Spanning Tree (MST), an optimal message and round complexity is achievable (up to polylog terms) by a single algorithm in the CONGEST model of communication.
• In this paper we provide algorithms that are simultaneously round- and message-optimal for a number of well-studied distributed optimization problems.