Towards Singular Optimality in the Presence of Local Initial Knowledge

The Knowledge Till \(\rho \) (in short, KT-\(\rho \)) Congest model is a variant of the classical Congest model of distributed computing in which each vertex v has initial knowledge of the radius-\(\rho \) ball centered at v. The most commonly studied variants of the Congest model are KT-\(0\) Congest in which nodes initially know nothing about their neighbors and KT-\(1\) Congest in which nodes initially know the IDs of all their neighbors. It has been shown that having access to neighbors IDs (as in the KT-\(1\) Congest model) can substantially reduce the message complexity of algorithms for fundamental problems such as BroadCast and MST. For example, King, Kutten, and Thorup (PODC 2015) show how to construct an MST using just \(\tilde{O}(n)\) messages in the KT-\(1\) Congest model for an n-node graph, whereas there is an \(\varOmega (m)\) message lower bound for MST in the KT-\(0\) Congest model for m-edge graphs. Building on this result, Gmyr and Pandurangan (DISC 2018) present a family of distributed randomized algorithms for various global problems that exhibit a trade-off between message and round complexity. These algorithms are based on constructing a sparse, spanning subgraph called a danner. Specifically, given a graph G and any \(\delta \in [0,1]\), their algorithm constructs (with high probability) a danner that has diameter \(\tilde{O}(D + n^{1-\delta })\) and \(\tilde{O}(\min \{m,n^{1+\delta }\})\) edges in \(\tilde{O}(n^{1-\delta })\) rounds while using \(\tilde{O}(\min \{m,n^{1+\delta }\})\) messages, where n, m, and D are the number of nodes, edges, and the diameter of G, respectively. In the main result of this paper, we show that if we assume the KT-\(2\) Congest model, it is possible to substantially improve the time-message trade-off in constructing a danner. Specifically, we show in the KT-\(2\) Congest model, how to construct a danner that has diameter \(\tilde{O}(D + n^{1-2\delta })\) and \(\tilde{O}(\min \{m,n^{1+\delta }\})\) edges in \(\tilde{O}(n^{1-2\delta })\) rounds while using \(\tilde{O}(\min \{m,n^{1+\delta }\})\) messages for any \(\delta \in [0,\frac{1}{2}]\). This result has immediate consequences for BroadCast, spanning tree construction, MST, Leader Election, and even local problems such as \((\varDelta +1)\)-coloring in the KT-\(2\) Congest model. For example, we obtain a KT-\(2\) Congest algorithm for MST that runs in \(\tilde{O}(D + n^{1/2})\) rounds, while using only \(\tilde{O}(\min \{m, n^{1 + 1/4}\})\) messages.

1. 1.

   We use \(\tilde{O}(\cdot )\) to absorb \(\text {polylog}(n)\) factors in \(O(\cdot )\) and \(\tilde{\varOmega }(\cdot )\) to absorb \(1/\text {polylog}(n)\) factors in \(\varOmega (\cdot )\).

2. 2.

   We use “w.h.p.” as short for “with high probability”, representing probability at least \(1 - 1/n^c\) for constant \(c \ge 1\).

3. 3.

   Note that this step requires 2-hop knowledge; all steps in our algorithms which assume 2-hop knowledge are highlighted in gray.

Authors and Affiliations

1. Department of Computer Science, The University of Iowa, Iowa City, IA, USA

   Hongyan Ji & Sriram V. Pemmaraju

Corresponding author

Correspondence to Sriram V. Pemmaraju .

Editors and Affiliations

1. Faculty of Data and Decision Sciences, Technion – Israel Institute of Technolog, Haifa, Israel

   Yuval Emek

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics