  The Knowledge Till 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 KT0 CONGEST in which nodes initially know nothing about their
neighbors and KT1 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
KT1 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
Otilde(n) messages in the KT1 CONGEST model, whereas there is an Omega(m)
message lower bound for MST in the KT0 CONGEST model. Building on this result,
Gmyr and Pandurangen (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 Otilde(D + n^{1-delta}) and Otilde(min{m,n^{1+delta}}) edges in
Otilde(n^{1-delta}) rounds while using Otilde(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
KT2 CONGEST model, it is possible to substantially improve the time-message
trade-off in constructing a danner. Specifically, we show in the KT2 CONGEST
model, how to construct a danner that has diameter Otilde(D + n^{1-2delta}) and
Otilde(min{m,n^{1+delta}}) edges in Otilde(n^{1-2delta}) rounds while using
Otilde(min{m,n^{1+\delta}}) messages for any delta in [0,1/2].
