Time-, Message- and Memory-Efficient Distributed Minimum Spanning Tree and Partwise Aggregation

Abstract

Memory-(in)efficiency is a crucial consideration that oftentimes prevents deployment of state-of-the-art distributed algorithms in real-life modern networks. In the context of the MST problem, roughly speaking, there are three types of algorithms. The GHS algorithm (Gallager et al. 1983) and its versions are memory- and message-efficient, but their running time is at least linear in the number of vertices n, even when the unweighted diameter D is much smaller than n. The GKP algorithm (Garay et al. 1998) and its versions are time-efficient, but not message- or memory-efficient. Several recent algorithms (Elkin 2020, Haeupler et al. 2018, Pandurangan et al. 2020) are time- and message-efficient, but are not memory-efficient. GHS-type algorithms are much more prominent in real-life applications, in part due to their relative simplicity, but also because memory-efficiency acts as a constraint. In this paper we develop a deterministic time-, message- and memory-efficient algorithm for the MST problem. Our algorithm is also applicable to the more general partwise aggregation problem. We believe that our techniques will be useful for devising memory-efficient algorithms to many other distributed problems.