\section{Introduction}\label{sec:introduction}
The overarching theme of this paper is laying down an algorithmic infrastructure and employing it for designing fast algorithms in seemingly unrelated distributed settings, namely, the classic \ensuremath{\mathsf{CONGEST}}\xspace model and the recently-introduced \ensuremath{\mathsf{Hybrid}}\xspace model. 

The \ensuremath{\mathsf{CONGEST}}\xspace model \cite{Peleg2000} abstracts a synchronous network of $n$ nodes, in which in each round of computation, each node can send a message of $O(\log n)$ bits on each of its links. A recent line of work addresses computing MST, distances, and data summarizaion in \ensuremath{\mathsf{CONGEST}}\xspace with \emph{low-mixing time} \cite{Ghaffari2017DistributedMA,Ghaffari2018NewDA,Su2019DistributedDS} and finding small graphs in \ensuremath{\mathsf{CONGEST}}\xspace benefits from efficient computation inside components of low-mixing time  \cite{Chang2019DistributedTD,ChangS19,ChangS20,Censor-HillelGL20,CensorHillelCLL20,EdenFFKO19,quantumCongestTriangles}. 
Low-mixing time is, in particular, a property of expander graphs, which have been shown to be useful for designing data centers \cite{Harsh2018ExpanderDF,DinitzSS20}.

The \ensuremath{\mathsf{Hybrid}}\xspace model, recently introduced by \cite{AHKSS20}, abstracts networks supporting
high-bandwidth communication over \emph{local} edges, as well as very low-bandwidth communication over \emph{global} edges. Aligned with most previous work on this model, we assume here unbounded bandwidth for messages to neighbors, and $O(\log n)$-bit messages to a constant number of nodes anywhere in the network. This model in particular abstracts recent developments in hybrid data centers \cite{Cui2011ChannelAI,HanHLX15,HuangLLPLL13,WangAKPNKR10}.
Most research in the \ensuremath{\mathsf{Hybrid}}\xspace model has been devoted to distance computation problems  \cite{AHKSS20,kuhn2020computing,feldmann2020fast,censorhillel2020distance}. 

While these settings highly differ, we pinpoint an approach that underlies computation in both settings, namely, \emph{sparsity and density awareness}. The key type of tasks which we tackle are tasks requiring transfer of massive amounts of data. 
Our general approach is to design load balancing mechanisms that leverage the full bandwidth of a given communication model.
Examples of tasks that enjoy our framework are matrix multiplication and distance computations.

\sloppy{For the purpose of our framework, as an auxiliary tool (not as a computational model in its own right), we define the \ensuremath{\mathsf{Anonymous\ Capacitated}}\xspace model with capacity $c$ (abbreviated \wacc), which is an all-to-all setting whose main characteristics are a limit on the bandwidth per node and the anonymity of nodes. To cope with the harsh nature of the \wacc model, which is needed in order to allow it to be efficiently simulated, we develop a distributed data structure and accompanying algorithms, dedicated towards load balancing and full utilization of the available bandwidth.}

We then show sparsity aware simulations of the \wacc model in the \ensuremath{\mathsf{CONGEST}}\xspace and \ensuremath{\mathsf{Hybrid}}\xspace settings. Specifically, the simulations focus on utilizing all the available bandwidth in the underlying models, even when given highly skewed inputs. Combined, these obtain our end results -- fast algorithms for distance computations in low-mixing time \ensuremath{\mathsf{CONGEST}}\xspace and in the \ensuremath{\mathsf{Hybrid}}\xspace model. 

~\\A first flavor of our end results: One of our main contributions is proving that the size $n$ of the graph is not fine-grained enough to capture the complexity of the all-pairs shortest-paths problem (APSP) in the \ensuremath{\mathsf{CONGEST}}\xspace model. While there is an $\tilde{\Omega}(n)$ lower bound for general graphs, even when allowing large approximation factors \cite{Nanongkai2014DistributedAA}, and a matching randomized algorithm giving an exact solution \cite{Bernstein2019DistributedEW}, we show that one can go \emph{significantly} below this complexity, depending on the minimal degree in the graph and its mixing time.

\begin{restatable}[$(3+\varepsilon)$-Approximation for APSP in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{sublinearAPSP}\label{cor:sublinearAPSP}
    For any constant $0 < \varepsilon < 1$, and weighted, undirected graph ${G}$ with minimal degree $\delta$ and mixing time $\tau_{\text{mix}}$,
    there is an algorithm in the \ensuremath{\mathsf{CONGEST}}\xspace model computing a $(3+\varepsilon)$ approximation to APSP on $G$ within
    $(n^{1/2} + n/\delta)\cdot \ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds\footnote{\label{footnote1}Note that there is a typo in the complexity stated for this theorem in the SPAA'21 proceedings.}, \whp
\end{restatable}

For any constant $0 < \gamma < 1$, consider a graph $G$ with $\delta = n^\gamma \cdot \tau_{\text{mix}}\cdot 2^{\littleOmega{\sqrt{\log{n}}}}$. Using \cref{cor:sublinearAPSP}, it is possible to approximate weighted, undirected APSP on $G$ in $n^{1/2}\cdot \ensuremath{\tmix\cdot \twosqlgnlglgn} + O(n^{1-\gamma})$ rounds, \whp, in the \ensuremath{\mathsf{CONGEST}}\xspace model, which is a major improvement over the linear general case. This approach is aligned with a  conclusion that is obtained by the single-source shortest paths (SSSP) algorithm of \cite{Ghaffari2018NewDA} that reflects that $n$ and the diameter $D$ are insufficient for capturing the complexity of SSSP. Our result suggests that for APSP the  dependence parameters could be  $n,\delta$ and $\tau_{\text{mix}}$, and this opens the complexity landscape of APSP in the \ensuremath{\mathsf{CONGEST}}\xspace model to much further exciting research.
\subsection{Our Contributions}
\subsubsection{Fast Algorithms for the \ensuremath{\mathsf{Hybrid}}\xspace Model}

The pioneering works of \cite{AHKSS20, kuhn2020computing} lay down technical foundations that show that utilizing \emph{both} the local and global edges in the \ensuremath{\mathsf{Hybrid}}\xspace model allows solutions which are much faster than algorithms which only use the local or global edges. One of their prime contributions is showing that
the complexity of exact and approximate APSP is $\tilde \Theta(n^{1/2})$ rounds.

The $\tilde \Theta(n^{1/3})$-round regime is also of importance in this model, as \cite{kuhn2020computing,censorhillel2020distance} show a variety of algorithms with this complexity. For diameter, a lower bound of $\tilde \Omega(n^{1/3})$ rounds for exact unweighted diameter and for a $(2-\varepsilon)$ approximation for weighted diameter is shown (the first lower bound in the \ensuremath{\mathsf{Hybrid}}\xspace model for a problem with a small output), matched with a $\tilde O(n^{1/3})$ round algorithm for a $(1+\varepsilon)$ approximation for unweighted diameter, and a $2$ approximation for weighted diameter. For weighted distances, $\tilde O(n^{1/3})$-round algorithms are shown for approximations from polynomially many sources, in addition to exact distances from $\tilde O(n^{1/3})$ sources.


Our main contribution in the \ensuremath{\mathsf{Hybrid}}\xspace model is breaking below $o(n^{1/3})$ rounds for a $(1+\varepsilon)$ approximation for weighted single source shortest paths (SSSP), which also implies a $(2+\varepsilon)$ approximation for weighted diameter. As we elaborate upon in the following subsections, this requires establishing an entire foundation of techniques which are a core contribution of the paper. 
We show the following algorithm which completes in $\tilde O(n^{5/17})$ rounds, \whp (as common,
\emph{high probability} is at least $1-n^{-c}$, for a constant $c>1$).

\begin{restatable}[$(1+\varepsilon)$-Approximation for SSSP in \ensuremath{\mathsf{Hybrid}}\xspace]{theorem}{approxSSSP}
\label{theorem:approxSSSP}
Given a weighted, undirected graph $G = (V, E)$, with $n = |V|$ and $m = |E|$, a value $0 < \varepsilon < 1$, and a source $s \in V$, there is a \ensuremath{\mathsf{Hybrid}}\xspace model algorithm computing a $(1+\varepsilon)$-approximation of SSSP from $s$, in $\tildeBigO{n^{5/17} / \varepsilon^9}$ rounds, \whp
\end{restatable}

Our results provide an interesting open question: what is the best round complexity for a $2$ approximation of the diameter? We show that for a $(2+\varepsilon)$ approximation, $o(n^{1/3})$ rounds suffice, while $(2-\varepsilon)$ requires $\tilde \Omega(n^{1/3})$ rounds, as stated above.



\subsubsection{Fast Algorithms for the \ensuremath{\mathsf{CONGEST}}\xspace Model}

As a warm-up, we illustrate the power of our \wacc model and its simulation in the \ensuremath{\mathsf{CONGEST}}\xspace model, by showing how to simulate the \ensuremath{\mathsf{Congested\ Clique}}\xspace model (a synchronous model where every two nodes can exchange messages of $O(\log n)$ bits in every round) in \wacc and hence in \ensuremath{\mathsf{CONGEST}}\xspace. Simulation of algorithms from the \ensuremath{\mathsf{Congested\ Clique}}\xspace model may both significantly simplify algorithm design as well as improve results in other distributed models, as seen in previous works \cite{Ghaffari2017DistributedMA,Chang2019DistributedTD,ChangS19,ChangS20,Censor-HillelGL20,CensorHillelCLL20,EdenFFKO19,kuhn2020computing}. 


We get the following result, from which one can already show new algorithms which beat the state-of-the-art in the \ensuremath{\mathsf{CONGEST}}\xspace model by simulating existing \ensuremath{\mathsf{Congested\ Clique}}\xspace algorithms. 

\begin{restatable}[\ensuremath{\mathsf{Congested\ Clique}}\xspace Simulation in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{cliqueInCongest}\label{cor:hc:cliqueSimulation}
    Consider a graph $G$. Let $A$  be an algorithm which runs in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model over $G$ in $t$ rounds. If each node $v$ has $\bigO{\deg{v}\cdot \log{n}}$ bits of input and output, then there is an algorithm which simulates $A$ in $(t\cdot {{n^2}/{m}})\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds of the \ensuremath{\mathsf{CONGEST}}\xspace model over $G$, \whp.
\end{restatable}


Here, $\tau_{\text{mix}}$ is the \emph{mixing time} of the graph, which is roughly the number of rounds required for a lazy random walk to reach the stationary distribution (a precise definition is not needed for understanding our results). A previous non trivial simulation of the \ensuremath{\mathsf{Congested\ Clique}}\xspace model in the \ensuremath{\mathsf{CONGEST}}\xspace model is due to~\cite{Ghaffari2017DistributedMA}. It emulates one \ensuremath{\mathsf{Congested\ Clique}}\xspace round in $O({n\cdot \tau_{\text{mix}}\cdot(1 + \frac{\Delta^2\log{n}\cdot\tau_{\text{mix}}}{n})\log{n}\log^*{n}})$ rounds of the \ensuremath{\mathsf{CONGEST}}\xspace model, where $\Delta$ is the maximum degree in the graph. Moreover, for certain graphs, this is improved to $\tilde O(n\cdot \tau_{\text{mix}})$.
Thus, our simulation improves upon both previous algorithms for all graphs with 
$m=n\cdot 2^{\littleOmega{\sqrt{\log{n}}}}$edges by a factor that is roughly proportional to the average degree, namely, faster by a factor of
$m / (n \cdot 2^{\alpha\cdot \sqrt{\log{n}}})$ for some constant $\alpha \geq 1$.
Intuitively, in \cite{Ghaffari2017DistributedMA}, if every node in \ensuremath{\mathsf{CONGEST}}\xspace desires to message every other node then this requires many rounds. We circumvent this by sending the input of low degree nodes to high degree ones, which then simulate the \ensuremath{\mathsf{Congested\ Clique}}\xspace model and send back the output to the low degree nodes.


\sloppy{Finally, such a simulation implies a relation between lower bounds in the \ensuremath{\mathsf{CONGEST}}\xspace and \ensuremath{\mathsf{Congested\ Clique}}\xspace models.} Specifically, simulating one \ensuremath{\mathsf{Congested\ Clique}}\xspace round in $T$ rounds of the \ensuremath{\mathsf{CONGEST}}\xspace model shows that a lower bound of $R$ rounds in the \ensuremath{\mathsf{CONGEST}}\xspace model implies a lower bound of $R/T$ rounds in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model. 
Due to \cite[Theorem 4]{DuckerPowerClique}, we know that lower bounds for some problems in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model imply lower bounds in bounded-depth circuit complexity, and are therefore considered hard to obtain.
Plugging our results from \Cref{cor:hc:cliqueSimulation} in the $R/T$ lower bound for the \ensuremath{\mathsf{Congested\ Clique}}\xspace model shows that if one constructs a family of graphs $\mathcal{G}$ with $m$ edges and $\tau_{\text{mix}}$ mixing time, for which solving some problem $P$ in the \ensuremath{\mathsf{CONGEST}}\xspace model requires $R$ rounds, then $P$ has a lower bound of $(R\cdot m/(n^2\cdot \tau_{\text{mix}}\cdot 2^{\alpha{\sqrt{\log{n}}}}))$
rounds in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model for some constant $\alpha \geq 1$. This means that any value of $\tau_{\text{mix}}$ that is below $R\cdot m/(n^2\cdot 2^{\alpha\sqrt{\log{n}}})$ implies a lower bound that is considered hard in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model. 

\paragraph{SSSP\@.}
The current state-of-the-art exact SSSP algorithm in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model, due to~\cite{SparseMMPODC2019}, runs in $O(n^{1/6})$ rounds. Using our result from \cref{cor:hc:cliqueSimulation}, a
simulation of this algorithm in the \ensuremath{\mathsf{CONGEST}}\xspace model runs in  $({n^{13/6}}/{m})\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp. We further improve this result by presenting a solution that is faster for any graph which is not extremely dense, namely, for which $m=\littleO{n^2}$. In a nutshell, our speed-up is due to the fact that the \ensuremath{\mathsf{Congested\ Clique}}\xspace algorithm does not use all of the $\Omega(n^2)$ bandwidth available to it in every round, and so it is inefficient to simulate directly in \ensuremath{\mathsf{CONGEST}}\xspace. Thus, we instead simulate our \wacc model, which better reflects the complexity of such algorithms, giving us the following. 
\begin{restatable}[Exact SSSP in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{exactSSSPInHC}\label{theorem:hc:exactSSSP}
    Given a weighted, undirected graph $G$ and a source node $s \in G$, there is an algorithm in the \ensuremath{\mathsf{CONGEST}}\xspace model that ensures that every node $v \in G$ knows the value $d_G(s, v)$, within ${(n^{7/6}/m^{1/2} + n^2/m)}\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp.
\end{restatable}



Consider graphs with a 
mixing time $\tau_{\text{mix}}=\tildeBigO{1}=\poly\log(n)$. The diameter $D$ of such graphs is also $\tildeBigO{1}$. If such a graph has at least $m = n^{3/2}\cdot 2^{\littleOmega{\sqrt{\log{n}}}}$ edges, then our SSSP algorithm runs asymptotically faster than the state-of-the-art $\tildeBigO{n^{1/2}D^{1/4}}$-round algorithm of~\cite{ChechikM20}.

\paragraph{APSP\@.}
We now turn our attention to the APSP problem. As observed by Nanongkai \cite[Observation 1.4]{Nanongkai2014DistributedAA}, to solve APSP in the \ensuremath{\mathsf{CONGEST}}\xspace model, a node $v$ is required to learn $\tildeBigO{n}$ bits of information. In the worst case, for a node with a constant degree, this takes $\tildeBigOmega{n}$ rounds. For this reason,  slightly modified requirements for the output have been considered.

We consider a \emph{shortest-path query problem}, in which we separate the computation of shortest paths into two phases, one in which the input graph is pre-processed, and another in which a query set of pairs of nodes is given, $Q \subseteq V \times V$, and every node $v$ is required to learn the distance to every node $u$ such that $(v, u) \in Q$. 
The round complexity of this problem is thus bi-criteria, measured both in terms of pre-processing time and in terms of query time. We analyze the round complexity of the query in terms of the \emph{query load}, where given a node $v$, $q_v = \size{\{u\ |\ (v, u) \in Q \lor (u, v) \in Q\}}$ denotes the number of queries which $v$ is a part of, and the total, normalized query load is $\ell = \max_{v \in V} q_v / \deg{(v)}$. 
\begin{restatable}[$(3+\varepsilon)$-Approximation for Shortest-Path Query in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{apspQuery}\label{claim:hc:apspQuery}
    For any constant $0 < \varepsilon < 1$ and a weighted, undirected graph $G$ with $m$ edges,
    there is a \ensuremath{\mathsf{CONGEST}}\xspace algorithm which after 
    $(n^{1/2} + {n^{11/6}}/{m})\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds
     of pre-processing, solves any instance of the $(3+\varepsilon)$-approximate shortest path query problem with a known load $\ell$, in $\ell\cdot \ensuremath{\tmix\cdot \twosqlgnlglgn} $ rounds, \whp.
\end{restatable}


By denoting $\delta$ as the minimal degree in the graph, one gets $\ell \leq n/\delta$ and $m \geq n \cdot \delta$, which implies \cref{cor:sublinearAPSP} stated above.

Finally, we consider a version of APSP, which we call \emph{Scattered APSP}, where the distance between every pair of nodes is known to \emph{some} node, not necessarily the endpoints themselves. That is, we require that every node $u$ knows, for every node $v$, the identity of a node $w_{uv}$, which stores the distance $d_{G}(u,v)$.
\begin{restatable}[$(3+\varepsilon)$-Approximation for Scattered APSP in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{SAPSPInHC}\label{theorem:hc:sapsp}
    There exists an algorithm in the \ensuremath{\mathsf{CONGEST}}\xspace model, that given a weighted, undirected
    input graph $G=(V, E)$ with $n = |V|$ and $m = |E|$, and some constant $0 < \varepsilon < 1$, solves the $(3+\varepsilon)$-approximate Scattered APSP problem on $G$,
    within $((n^{11/6}/m + n^{1/3} + m / n)/\varepsilon + n^{1/2})\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds\footnote{See footnote~\ref{footnote1}.}, \whp 
\end{restatable}

\paragraph{Roadmap.} After a survey of additional related work, \Cref{sec:prelim} provides required definitions. Additional preliminaries appear in \Cref{app:prelim}. \Cref{sec:wacc} is dedicated to the definition of carrier configurations in the \wacc model, and for a flavor of a sample proof, namely, sparse matrix multiplication. The bulk of our infrastructure for \wacc is deferred to \Cref{app:sec:wacc}. Finally, \Cref{sec:subCubeRootAlgorithms} and \Cref{sec:congest} provide proofs of our end results in the \ensuremath{\mathsf{Hybrid}}\xspace and \ensuremath{\mathsf{CONGEST}}\xspace models, respectively. Both sections have some content deferred to \Cref{app:littleO} and \Cref{app:sec:congest}, respectively. We conclude with a discussion in \Cref{sec:discussion}.


\subsection{Additional Related Work}




\paragraph{\ensuremath{\mathsf{Hybrid}}\xspace.}

There is growing interest in the recently introduced \ensuremath{\mathsf{Hybrid}}\xspace network model \cite{AHKSS20}. It is further studied by \cite{kuhn2020computing,feldmann2020fast,censorhillel2020distance}. \cite{AHKSS20,kuhn2020computing,censorhillel2020distance} consider the same values for the local bandwidth $\lambda$ and global bandwidth $\gamma$ as we do, and address mainly distance computations. 
The complexity of exact weighted APSP is $\tildeTheta{n^{1/2}}$ rounds, by combining the upper bound of \cite{kuhn2020computing}, and the lower bound of \cite{AHKSS20}. The complexity of $3$ approximate weighted $n^{2/3}$-SSP is $\tildeTheta{n^{1/3}}$ rounds, by combining the upper bound of \cite{censorhillel2020distance}, and the lower bound of \cite{kuhn2020computing}.
\cite{AHKSS20,kuhn2020computing} show how to simulate one round of the \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace (a synchronous distributed model where every node can broadcast a (same) $O(\log n)$-bit message to all nodes per round) and \ensuremath{\mathsf{Congested\ Clique}}\xspace models on the skeleton graph with $\tildeBigO{n^{2/3}}$ nodes in $\tildeBigO{n^{1/3}}$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model and obtain various distance related results using them. For example \cite{kuhn2020computing} show $(7+\varepsilon)$ and $(3+\varepsilon)$ weighted $n^{x}$-SSP approximation in $O(n^{1/3}/\varepsilon)$ and $\tildeBigO{n^{0.397 + n^{x/2}}}$ rounds  \whp, respectively. \cite{censorhillel2020distance} improve on some of those results by simulating ad-hoc models which exploit additional communication abilities of the \ensuremath{\mathsf{Hybrid}}\xspace model. For instance, they show $3$ approximate weighted $n^{x}$-SSP approximation in $O(n^{1/3}/\varepsilon)$ rounds \whp.
\cite{feldmann2020fast} solve distance problems for sparse families of graphs using local congestion bounded by $\log{n}$. Another special case of the \ensuremath{\mathsf{Hybrid}}\xspace model is the \ensuremath{\mathsf{Node\text{-}Capacitated\ Clique }}\xspace model, which contains only global edges
\cite{AugustineCCPSS20,AGGHKL19}.






\paragraph{\ensuremath{\mathsf{CONGEST}}\xspace.}
Distance problems are extensively studied in the \ensuremath{\mathsf{CONGEST}}\xspace model due to being fundamental tasks. One of the important problems in the \ensuremath{\mathsf{CONGEST}}\xspace model is $(1+\varepsilon)$-approximate SSSP \cite{Sarma2011DistributedVA,Becker2017NearOptimalAS,Henzinger2019ADA}. The state-of-the-art randomized algorithm  \cite{Becker2017NearOptimalAS} solves it in $\tildeBigO{(\sqrt{n} + D)\varepsilon^{-3}}$ rounds \whp, even in the more restricted Broadcast \ensuremath{\mathsf{CONGEST}}\xspace model. This is close to the $\tilde{\Omega}{(\sqrt{n} + D)}$ lower bound  by \cite{Sarma2011DistributedVA}. The state-of-the-art deterministic algorithm \cite{Henzinger2019ADA} completes in $n^{1/2 + o(1)} + D^{1 + o(1)}$ rounds.  The complexity of exact SSSP is still open, with algorithms  given in \cite{Elkin2017DistributedES,Ghaffari2018ImprovedDA,Forster2018AFD,ChechikM20}. The current best known algorithm is of \cite{ChechikM20} runs in $\tildeBigO{n^{1/2}D^{1/4} + D}$ rounds, \whp.

There is a lower bound of $\tildeBigOmega{n}$ rounds to compute APSP \cite{Nanongkai2014DistributedAA} which was then tweaked to give a $\bigOmega{n}$ lower bound for the weighted case \cite{CensorHillelKP17}. Over the years there was much progress in understanding the complexity of this problem \cite{Peleg2012DistributedAF,Lenzen2013EfficientDS,Lenzen2015FastPD,Agarwal2018ADD,Elkin2017DistributedES,Bernstein2019DistributedEW,Agarwal2019DistributedWA,Ramachandran20FasterDA}. For  weighted exact APSP, the best known  randomized algorithm \cite{Bernstein2019DistributedEW} is optimal up to polylogarithmic terms. The best deterministic algorithm to  date \cite{Ramachandran20FasterDA} completes in $\tildeBigO{n^{4/3}}$ rounds. For unweighted exact APSP, $\tildeBigO{n}$ rounds algorithms are known \cite{Peleg2012DistributedAF,Lenzen2013EfficientDS,HolzerW12}.

To go below the $\bigOmega{n}$ lower bound, \cite{Lenzen2013FastRT,Lenzen2015FastPD} propose to build name-dependent routing tables and APSP. This means that the algorithm is allowed to choose small labels and output results that are consistent with those labels. Choosing the labels carefully thus overcomes the need to send too many bits of information to low-degree nodes. There is also a line of work which breaks below the lower bound for some certain graph families \cite{GhaffariH16PODC,GhaffariH16SODA,LiP19,Parter20a}.
\cite{Peleg2012DistributedAF,Frischknecht2012NetworksCC,Abboud2016NearLinearLB,GrossmanKP20,Ancona2020DistributedDA} study exact and approximate diameter, eccentricities, girth and other problems. 

Recently, \cite{Ghaffari2017DistributedMA,Ghaffari2018NewDA,Su2019DistributedDS} noticed that it is possible to develop faster \ensuremath{\mathsf{CONGEST}}\xspace algorithms when the underlying graph has low mixing time. This was shown for MST \cite{Ghaffari2017DistributedMA}, maximum flow, SSSP and transshipment \cite{Ghaffari2018NewDA} and frequency moments \cite{Su2019DistributedDS}. Algorithms for subgraph-freeness and related variants also enjoy fast computations on graphs with low mixing time \cite{Chang2019DistributedTD,quantumCongestTriangles,ChangS19,Chang2019DistributedTD,ChangS19,ChangS20,Censor-HillelGL20,CensorHillelCLL20,EdenFFKO19}.

\paragraph{\ensuremath{\mathsf{Congested\ Clique}}\xspace and \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace.}
In the \ensuremath{\mathsf{Congested\ Clique}}\xspace and \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace models, distance related problems like APSP, $k$-SSP and diameter and their approximation are studied in \cite{Nanongkai2014DistributedAA,CensorHillel2016AlgebraicMI,Gall2016FurtherAA,CensorHillel2020SparseMM,SparseMMPODC2019,Dory2020ExponentiallyFS,Holzer2015ApproximationOD,Becker2017NearOptimalAS}.
We mention that models related to the \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace and \ensuremath{\mathsf{Congested\ Clique}}\xspace models have been studied in~\cite{Becker2015BriefAA,Becker2016TheEffectOf}, who explore the regime between broadcast and unicast.


\addtocontents{toc}{\protect\setcounter{tocdepth}{2}}

\section{Preliminaries}\label{sec:prelim}
The following are some required definitions, while \Cref{app:prelim} contains additional definitions and basic claims.
We begin with a variant of the \ensuremath{\mathsf{Hybrid}}\xspace model, introduced in \cite{AHKSS20}.

\begin{definition}[\ensuremath{\mathsf{Hybrid}}\xspace Model]

In the \ensuremath{\mathsf{Hybrid}}\xspace model, a synchronous network of $n$ nodes with identifiers in \interval{n} is given by a graph $G=(V,E)$. In each round, every node can send and receive $\lambda$ messages of $O(\log n)$ bits to/from each of its neighbors (over \emph{local edges} $E$) and an additional $\gamma$ messages in total that are $\bigO{\log{n}}$ bits long to/from any other nodes in the network (over \emph{global edges}). If in some round more than $\gamma$ messages are sent via global edges to/from a node, only $\gamma$ messages selected adversarially are delivered.
\end{definition}

All of \cite{AHKSS20,kuhn2020computing,censorhillel2020distance} use $\lambda=\infty,\gamma=\log{n}$. To our knowledge only \cite{feldmann2020fast} considers more restrictive settings of $\lambda=1,\gamma=\log{n}$.

We introduce the \ensuremath{\mathsf{Anonymous\ Capacitated}}\xspace model with capacity $c$ (abbreviated \wacc), which we show is powerful for extracting core distributed principles. The model has two defining characteristics which are \emph{anonymity} and \emph{restricted message capacity}. 

\begin{definition}[The \wacc Model]
\label{def:wacc}
    The \ensuremath{\mathsf{Anonymous\ Capacitated}}\xspace model with capacity $c$ is a distributed synchronous communication model, over a graph $G=(V, E)$ with $n$ nodes, where each node $v$ can send and receive $c$ messages in every round, each of size $O(\log n)$ bits, to and from any node in the graph. Nodes have identifiers in $[n]$, however, every node has a unique $O(\log n)$-bit, \emph{communication token}, initially known only to itself. Node $v$ can send each message either to some node $w$ whose communication token is already known to $v$, or, to a node selected uniformly, independently at random from the entire graph.
    \end{definition}

\wacc[c] bears some similarity to the $\ensuremath{\nccshort_0}\xspace$ model \cite{AugustineCCPSS20} with an empty \emph{initial knowledge graph}. Unlike the $\ensuremath{\nccshort_0}\xspace$ model, \wacc[c] has additional capacity to send $c$ messages from each node and ability to send messages to random nodes. Our motivation for defining \wacc is to provide a setting which is both strong enough in order to solve challenging problems, yet, at the same time is weak enough in order to be simulated efficiently in the settings of interest. 
We note the importance of having both identifiers and communication tokens. An identifier is chosen from a given, hardcoded set and thus can be used for assigning tasks to specific nodes. Communication tokens both assist in dealing with anonymity, and enhance the ability of the \wacc model to be easily simulated in other distributed settings -- \emph{a simulating algorithm can encode routing information of the underlying model in the tokens}. 





~\\
Many of our results hold for weighted graphs $G=(V, E, w)$, where $w\colon E\mapsto \set{1, 2, \dots, W}$ for a $W$ which is polynomial in $n$. Whenever we \emph{send} an edge $e$ as part of a message, we assume $w(e)$ is sent as well. We assume that all graphs that we deal with are connected.

Given a graph $G=(V, E)$ and a pair of nodes $u, v\in V$, we denote by $hop(u,v)$ the hop distance between $u$ and $v$, by $N^k_G(v)$ a subset of the $k$ closest nodes to $v$ with ties broken arbitrarily,
and by $d_G^h(u, v)$ the weight of the lightest path between $u$ and $v$ of at most $h$-hops, where if there is no path of at most $h$-hops then $d_G^h(u, v)=\infty$. In the special case of $h=\infty$,
we denote by $d_G(u, v)$ the weight of a lightest path between $u$ and $v$. We also denote by $\deg_{G}{(v)}$ the degree of $v$ in $G$, and, in the directed case, $\deg_{G}^{in}{(v)},\ \deg_{G}^{out}{(v)}$ denote the in-degree and out-degree of $v$ in $G$, respectively. When it is clear from the context we sometimes drop the subscript $G$.



\begin{definition}[$k$-Source Shortest Paths (k\textsc{-SSP}\xspace)]
    Given a graph $G = (V, E)$, in the \emph{$k$-source shortest path problem}, we are given a set $S\subseteq V$ of $k$ sources. Every $u\in V$ is required to learn the distance $d_G(u, s)$ for each source $s\in S$. The cases where $k=1$, $k=n$ are called the \emph{single source shortest paths} problem (SSSP), and \emph{all pairs shortest paths} problem (APSP), respectively.
\end{definition}

\begin{definition}[Scattered APSP]
\label{def:scatteredAPSP}
Given a graph $G = (V, E)$, in the \emph{Scattered APSP} problem, for every pair of nodes $u, v \in V$, there exist nodes $w_{uv}, w_{vu} \in V$ (potentially $w_{uv} = w_{vu}$), such that $w_{uv}$ and $w_{vu}$ know $d_G(u, v)$, $u$ knows the identifier of $w_{uv}$, and $v$ knows the identifier of $w_{vu}$. 
\end{definition}

In the approximate versions of these problems, each $u\in V$ is required to learn an $\left(\alpha,\beta\right)$-approximate distance $\widetilde{d}(u, v)$ which satisfies $d(u, v)\leq \widetilde{d}(u, v) \leq \alpha \cdot d(u, v) + \beta$, and in case $\beta=0$, $\widetilde{d}(u, v)$ is called an $\alpha$-approximate distance.


\begin{definition}[Diameter]
    Given a graph $G=(V, E)$, the diameter $D=\max_{u,v\in V}\set{d(u,v)}$ is the maximum distance in the graph. An $\alpha$-approximation of the diameter $\widetilde{D}$ satisfies $D/\alpha\leq\widetilde{D}\leq D$. 
\end{definition}




\section{The \ensuremath{\mathsf{Anonymous\ Capacitated}}\xspace Model}
\label{sec:wacc}


The role of defining the \wacc model is its power given by our ability to efficiently simulate it 
in the \ensuremath{\mathsf{Hybrid}}\xspace and \ensuremath{\mathsf{CONGEST}}\xspace models. Applications of this strength are exemplified by improved algorithms for distance computation problems in these models.

To this end, we design fast algorithms in the \wacc model for the useful tools of sparse matrix multiplication and hopset construction (\cref{wacc:main:results}). Such algorithms already exist in all-to-all communication models, such as the \ensuremath{\mathsf{Congested\ Clique}}\xspace \cite{SparseMMPODC2019,Dory2020ExponentiallyFS}. However, fundamental load balancing and synchronization steps that are simple to implement when assuming a bandwidth of $\Theta(n^2)$ messages per round as in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model, provide formidable challenges when nodes cannot receive $\Theta(n)$ messages each. For instance, when multiplying two matrices, while the number of finite elements in row $v$ of both input matrices might be small, in the output matrix, row $v$ might be very dense, so that node $v$ would not be able to learn all of this information. This even implies that it is not always the case that every node can even know about all the edges incident to it in some overlay graph (e.g., a hopset). 
The crux in the way we overcome these challenges is in introducing the \emph{carrier configuration} distributed data structure that performs automatic load balancing (\cref{subsec:carrierConfiguration}). 
Missing proofs are deferred to \cref{app:sec:wacc}.

\subsection{Carrier Configurations}\label{subsec:carrierConfiguration}

A carrier configuration is a distributed data structure for holding graphs and matrices, whose main objective is to provide a unified framework for load balancing in situations where substantial amounts of data need to be transferred. The key is that when using the carrier configurations data structure, an algorithm does not need to address many load balancing issues, as those are dealt with under-the-hood by the data structure itself. Therefore, this data structure allows us to focus on the core concepts of each algorithm and abstract away challenges that arise due to skewed inputs.

The data structure crucially enables our algorithms to enjoy sparsity awareness, by \emph{yielding complexities that depend on 
the average degree in an input graph rather than its maximal degree}.
This allows one to eventually deal with data which is \emph{highly skewed} and which would otherwise cause a slow-down by having some nodes send and receive significantly more messages than others.

We stress that the manner in which we implement carrier configurations is inherently distributed in nature. In many cases, when two nodes $u,\ v$ store data, $D(u),\ D(v)$, respectively, in a carrier configuration, the data is dispersed among many other nodes, and when operations are performed using both $D(u)$ and $D(v)$, the nodes which store the data perform direct communication between themselves, without necessarily involving $u$ or $v$.


In more detail, the carrier configuration data structure is based on three key parts. (1) \emph{Carrier Nodes:} every node $v$ gets a set $C_v$ of \emph{carrier nodes}, where $|C_v| = \Theta(\deg(v)/k)$ and $k$ is the average degree in the graph, which \emph{help} $v$ to carry information and store its input edges in a distributed fashion. A key insight is that it is possible to create such an assignment of carrier nodes and also maintain that each node itself is not a carrier for too many other nodes, thus avoiding congestion. (2) \emph{Ordered Data Storage:} the data of $v$ is stored in a sorted fashion across $C_v$ in order to enable its efficient usage. In particular, it takes $O(\log n)$ bits in order to describe what ranges of data are stored in a specific carrier node. (3) \emph{Communication Structure:} the nodes $C_v \cup \{v\}$ are connected using a communication tree (\cref{definition:communicationTree}), which enables fast broadcasting and aggregation of information between $v$ and $C_v$.

A formal definition of a \emph{carrier configuration data structure} (\cref{definition:carrierConfiguration}), as well as an extended \wacc-specific definition (\cref{wacc:def:carrierConfiguration}) are given in \cref{subsec:waccAppCarconf}.


\textbf{Carrier Configuration Toolbox.} Typically, data is converted from a \emph{classical} storage setting (every node knows the edges incident to it) into being stored in a carrier configuration, and then operations are applied to change the state of the configuration.
Thus, we show in the \wacc model how to convert a classical graph representation to a carrier configuration. Then, we provide basic tools, e.g., given two matrices held in carrier configurations, produce a third configuration holding the matrix resulting from computing the point-wise minimum of the two input matrices. The descriptions and implementations of these are deferred to \cref{app:wacc:carrierconfiguration}.


\subsection{Sparsity Aware Distance Computations}
\label{wacc:main:results}

In order to give a taste of the type of algorithms which we construct in the \wacc model, we present an outline of our \emph{sparse matrix multiplication} algorithm. 


We build a foundation in the \wacc model
which enables us to eventually implement sparse matrix multiplication and hopset construction algorithms, as inspired by the \ensuremath{\mathsf{Congested\ Clique}}\xspace model algorithms in \cite{SparseMMPODC2019},\footnote{We note that while some results of \cite{SparseMMPODC2019} were improved in \cite{Dory2020ExponentiallyFS}, the improvements focus on reducing the amount of synchronous rounds of the algorithm, yet do not decrease the message complexity in way that assists us.}  in order to solve distance related problems. Ultimately, compared to \cite{SparseMMPODC2019}, our main contribution is significantly reducing the \emph{message} complexity overhead of the load balancing mechanisms. In the \ensuremath{\mathsf{Congested\ Clique}}\xspace implementation, various load balancing steps require $\Theta(n^2)$ messages, which is trivial in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model, yet is highly problematic in the \wacc model (and in the \ensuremath{\mathsf{CONGEST}}\xspace and \ensuremath{\mathsf{Hybrid}}\xspace models which ultimately simulate it). Interestingly, for the relevant sparsity used in distance computations, the sparse matrix multiplication itself requires $o(n^2)$ messages for actual transfer of matrix elements, and in the \ensuremath{\mathsf{Congested\ Clique}}\xspace algorithm, the message complexity is dominated by the $\Theta(n^2)$ overhead. We reduce this overhead significantly such that the message complexity of the algorithm is dominated by the messages which actually transfer matrix elements.


We show how to perform sparse matrix multiplication in the \wacc model. To simplify our proofs, we assume that the two input matrices and the output matrix have the same average number of finite elements per row.
We note that it is possible to use the same ideas we show here in order to prove the general case where the matrices have different densities.

\begin{restatable}[Sparse Matrix Multiplication]{theorem}{SparseMM}\label{theorem:wacc:sparseMM}
Given two $n \times n$ input matrices $S, T$, both with an average number of \emph{finite} elements per row of at most $k$, and stored in carrier configurations, $A$ and $B$, it is possible to output the matrix $\hat P$, in carrier configuration $C$, where $\hat P$ is $P = S \cdot T$, with only the smallest $k$ elements of each row computed, breaking ties arbitrarily.
This takes $\tilde O(k \cdot n^{1/3}/c + n/(k\cdot c) + 1)$ rounds, in the \wacc model, \whp \end{restatable}

\begin{proofof} {\cref{theorem:wacc:sparseMM}}
Throughout the algorithm, we assume that every piece of data \emph{sent directly} to a node is also known by all its carrier nodes. This is possible to do with only a $\tilde O(1)$ multiplicative factor to the round complexity, due to \fullref{lemma:carrierConfiguration:broadcastAggregate}. Further, as the input matrices are stored in carrier configuration, due to \cref{itm:carrierConfiguration:communicationToken}, every entry $S[i][j]$ is stored in $A$ alongside the communication tokens of both $i$ and $j$ (likewise for entries of $T$ stored in $B$). Thus, whenever a value is sent in the algorithm from one of the input matrices, we assume that it is sent alongside these communication tokens.

Denote by $\Delta$ the maximal number of finite elements in a row of $S$ or $T$. In the proof below, we show a round complexity of $\tilde O(k \cdot n^{1/3}/c + n/(k\cdot c) + \Delta / (n^{1/3} \cdot c) + n^{2/3}/c + 1)$, which is bounded by the claimed round complexity of $\tilde O(k \cdot n^{1/3}/c + n/(k\cdot c) + 1)$.\footnote{Notice that $\tilde O(k \cdot n^{1/3}/c + n/(k\cdot c) + \Delta / (n^{1/3} \cdot c) + n^{2/3}/c + 1) = \tilde O(k \cdot n^{1/3}/c + n/(k\cdot c) + 1)$, since: 1) It always holds that $\Delta \leq n$, and so $\Delta / (n^{1/3}\cdot c) = O(n^{2/3}/c)$, and 2) If $k < n^{1/3}$, then $n^{2/3}/c = O(n/(k \cdot c))$, yet if $k \geq n^{1/3}$, then $n^{2/3}/c = O(k \cdot n^{1/3}/c)$.}

Throughout the proof, we construct various sets of nodes (for instance, $V_{i}$) where every node in the set knows the communication tokens and identifiers of all the other nodes in the set ($Tokens(V_i)$), and thus we assume that the nodes in the each set locally compute some arbitrary node (some fixed $v_i \in V_i$) which is the \emph{leader} of the set. 
~\\

\noindent\textbf{Step: Partitioning the Input -- Sets $V_i$}\ \\
Denote by $\deg_S(v),\ \deg_T(v)$ the number of finite elements in row $v$ of $S$, and column $v$ of $T$, respectively.


Denote $W_1, \dots, W_{n^{1/3}/2}$, a hardcoded partition of $V$ into equally sized sets. Using \fullref{wacc:tools:routing} and \fullref{wacc:tools:grouping}, every $v \in W_i$ broadcasts $\deg_S(v),\ \deg_T(v)$ to $W_i$, within $O(n^{2/3}/c + 1)$ rounds. The nodes in $W_i$ locally partition $W_i$ into $W_{i, 1}, \dots, W_{i, j_i}$, for some $j_i$, where for each $k \in [j_i]$, $\sum_{v \in W_{i, k}} \deg_S(v) + \deg_T(v) \leq 4k \cdot n^{2/3} + 4\Delta$. Since $\sum_{v \in V}\deg_S(v) + \deg_T(v) \leq 2nk$, there exists a way to create this partitioning such that $\sum_{i \in [n^{1/3}]} j_i \leq n^{1/3}$. 

From here on, we refer to the sets $W_{i, k}$ as $V_j$. We denote by $S[V_j]$ the rows of $S$ corresponding to the nodes $V_j$, and by $T[V_j]$ the columns of $T$ corresponding to the nodes $V_j$. As $\sum_{i \in [n^{1/3}]} j_i \leq n^{1/3}$, there are at most $n^{1/3}$ sets $V_i$ -- the sets $V_1, \dots, V_{n^{1/3}}$.
For each set $V_{i}$, an arbitrary $v_{i} \in V_{i}$ is designated as its \emph{leader}. The identifiers and communication tokens of all the leaders are broadcast using \fullref{wacc:tools:broadcasting}, within $\tilde O(n^{1/3}/c + 1)$ rounds.

We partition the information held by the sets $V_i$. We compute $C_i = \{0 = c_0, c_1, \dots c_{n^{1/3}/4-1}, c_{n^{1/3}/4} = n\}$, where the total number of finite entries in\footnote{The notation $S[X][a:b]$ denotes all rows of $S$ with indices in $X$, from column $a$ to column $b$.} $S[V_i][c_j+1:c_{j+1}]$ is at most $16k \cdot n^{1/3} + 16\Delta/n^{1/3} + |V_i| \leq 16k \cdot n^{1/3} + 16\Delta/n^{1/3} + 2n^{2/3}$. Recall that for each $V_i$, it holds that $\sum_{v \in V_i} \deg_S(v) + \deg_T(v) \leq 4k \cdot n^{2/3} + 4\Delta$, and also $|V_i| \leq 2n^{2/3}$, implying the existence of such a set $C_i$. 

The nodes in $V_i$ compute the values in $C_i$ using binary search. To see this, given any $p_1, \dots, p_c$, the number of finite entries in each of $S[V_i][0:p_1], \dots, S[V_i][0:p_c]$ can be computed by the nodes in $V_i$ in $\tilde O(1)$ rounds, using \fullref{wacc:tools:groupBroadcasting}. Thus, each $c_j \in C_i$ can be found using binary search, with $c$ binary searches run in parallel in $\tilde O(1)$ rounds. In total $\tilde O(|C_i|/c + 1) = \tilde O(n^{1/3}/c + 1)$ rounds are required to compute $C_i$.
~\\

\noindent\textbf{Step: Creating Intermediate Representations  -- Sets $U_{i, j}$, $P_{i, j, \ell}$ Matrices}\ \\
Let $U_{i, j}$, for $i, j \in [n^{1/3}]$, be a hard-coded partition of $V$ into equally sized sets. The goal of this step is for nodes $U_{i, j}$ to compute an \emph{intermediate representation} of the product $S[V_i]\times T[V_j]$. Therefore, we desire that each $V_i$ sends all its data to $U_{i, j}, U_{j, i}$, for each $j \in [n^{1/3}]$, in some load-balanced manner. We show how, for each $i \in [n^{1/3}]$, $V_i$ sends $S[V_i]$ to $U_{i, j}$, for each $j \in [n^{1/3}]$, and in a symmetric way (with matrix $T$ instead of $S$) this can be done for $U_{j, i}$.

In $\tilde O(n^{2/3}/c + 1)$ rounds, allow communication within each $U_{i, j}$ by invoking \fullref{wacc:tools:grouping}. Let some $u_{i, j} \in U_{i, j}$, be denoted \emph{leader}, and broadcast the leaders of all the sets using \fullref{wacc:tools:broadcasting} within $\tilde O(n^{2/3}/c + 1)$ rounds. Node $u_{i, j}$ sends to both $v_i, v_j$ all of $Tokens(U_{i, j})$. Each node $v_i$ receives $n^{2/3}$ messages, thus this takes $\tilde O(n^{2/3}/c + 1)$ rounds using \fullref{wacc:tools:routing}. Now, each node $v_i$ broadcasts to $V_i$ all the tokens it receives, using \fullref{wacc:tools:groupBroadcasting}, within $\tilde O(n^{2/3}/c + 1)$ rounds.

Leader $v_i$ sends the contents of $C_i$ to all the leader nodes $u_{i, j}, u_{j, i}$, for any $j \in [n^{1/3}]$, in $\tilde O(n^{2/3}/c + 1)$ rounds using \fullref{wacc:tools:routing}. Each $u_{i, j}$ broadcasts to $U_{i, j}$ the contents of $C_i$ and $C_j$, within $\tilde O(n^{1/3}/c + 1)$ rounds using \fullref{wacc:tools:groupBroadcasting}.

We send information from $V_i$ to $U_{i, j}$. The $\ell$-th node in $U_{i, j}$ learns the finite elements in $S[V_i][c_\ell+1:c_{\ell+1}]$. By definition of $C_i$, for any $\ell$, the number of finite elements in $S[V_i][c_\ell+1:c_{\ell+1}]$ is at most $16k \cdot n^{1/3} + 16\Delta/n^{1/3} + 2n^{2/3}$, bounding the number of messages each node desires to receive. Every finite element held by a node $v \in V_i$ needs to be sent to $O(n^{1/3})$ nodes in the graph, in total.
Further, since the finite elements of $v$ are stored in its carrier nodes, and each carrier node of $v$ stores $O(k)$ elements, each node sends at most a total of $O(k \cdot n^{1/3})$ messages. Thus, this routing can be accomplished in $\tilde O(k\cdot n^{1/3}/c + \Delta/(n^{1/3} \cdot c) + n^{2/3}/c + 1)$ rounds, using \fullref{wacc:tools:routing}.\footnote{To perform the routing, it is required that the carrier nodes of $v \in V_i$ know the communication tokens of the nodes in $U_{i, j}$ which receive the messages. All the nodes in $V_i$ received $Tokens(U_{i,j})$, and so $v$ knows the required tokens. At the start of the proof, we state that we assume that every message a node receives is also broadcast from it to its carriers, and so also the carriers of $v$ know the required communication tokens.}. 


We shuffle data within $U_{i, j}$. Recall that $|U_{i, j}| = n^{1/3}$. The first $|C_i| = |C_j| = n^{1/3}/4$ nodes of $U_{i, j}$ received data from $S[V_i],\ T[V_j]$, according to
$C_i, C_j$. Denote $C_{i, j} = C_i \cup C_j$.
We desire that for each interval, $[c_\ell + 1, c_{\ell+1}]$, for $c_\ell \in C_{i, j}$, node $\ell \in U_{i, j}$ knows all the elements $S[V_i][c_\ell + 1, c_{\ell+1}]$ and $T[c_\ell + 1, c_{\ell+1}][V_j]$. To do so, notice that $S[V_i][c_\ell + 1, c_{\ell+1}]$ (likewise with $T$) is fully contained in the data which some node in $q \in U_{i, j}$, where $q \in [n^{1/3}/4]$ already knows.
Thus, each node $\ell \in [n^{1/3}/4]$ of $U_{i, j}$ denotes by $val(\ell)$ how many other nodes in $U_{i, j}$ are reliant on the data which it itself received from $V_i$.\footnote{This can be done since all the nodes in $U_{i, j}$ know all of $C_{i, j}$.} Then, we invoke \fullref{wacc:tools:groupMulticasting} in $\tilde O(k\cdot n^{1/3}/c + \Delta/(n^{1/3} \cdot c + n^{2/3}/c + 1)$ rounds in order to route the required information. Finally, each node $\ell \in [n^{1/3}/2]$ from $U_{i, j}$ knows $S[V_i][c_\ell + 1, c_{\ell+1}]$ and $T[c_\ell + 1, c_{\ell+1}][V_j]$, denoted $S_{i, j, \ell}, T_{i, j, \ell}$, respectively, and can compute the product $P_{i, j, \ell} = S_{i, j, \ell} \times T_{i, j, \ell}$.

We are at a state where for each $U_{i, j}$, every $\ell \in [n^{1/3}/2]$ of $U_{i, j}$ knows some matrix $P_{i, j, \ell}$ such that $S[V_i]T[V_j] = \sum_{\ell \in [n^{1/3}/2]}P_{i, j, \ell}$.\ \\

\noindent\textbf{Step: Sparsification -- $\hat{P}_{i, j, \ell}$ Matrices}\ \\
We sparsify the $P_{i, j, \ell}$ matrices. Recall that we desire to output $\hat P$ which is $P = S\times T$, with only the $k$ smallest entries on each row.
Fix $i \in [n^{1/3}]$, $\ell \in [n^{1/3}/2]$, and denote by $Q_{i, \ell}$ as the matrix of size $|V_i| \times n$ created by concatenating $P_{i, 0, \ell}, \dots, P_{i, n^{1/3}, \ell}$.
As shown in \cite{SparseMMPODC2019},
we are allowed to keep only the $k$ smallest entries on each row of $Q_{i, \ell}$, without damaging the final output $\hat{P}$. That is, throwing out elements at this stage is guaranteed to throw out elements which are only in $P$ and not in $\hat{P}$.


Fix $i \in [n^{1/3}], \ell \in [n^{1/3}/2]$, and denote by $N_{i, \ell}$ the nodes numbered $\ell$ in each $U_{i, j}$. The nodes in  $N_{i, \ell}$ perform a binary search for each row of $Q_{i, n^{1/3}, \ell}$, to determine the cutoff for the $k^{th}$ smallest element on that row.
The leaders $u_{i, 0}, \dots, u_{i, n^{1/3}}$ broadcast to each other $Tokens(U_{i, j}), \dots, Tokens(U_{i, n^{1/3}})$, using \fullref{wacc:tools:routing}, taking $O(n^{2/3}/c + 1)$ rounds. Each leader $u_{i, j}$ broadcasts the $O(n^{2/3})$
tokens it received to $U_{i, j}$, using \fullref{wacc:tools:groupBroadcasting}, within $\tilde O(n^{2/3}/c + 1)$ rounds. Now, the nodes $N_{i, \ell}$ all know $Tokens(N_{i, \ell})$.

The nodes $N_{i, \ell}$ proceed in $\tilde O(1)$ iterations to perform concurrent binary searches on the threshold values for each row in $Q_{i, \ell}$.
Let $n_{i, \ell}$ be an arbitrarily chosen leader node for $N_{i, \ell}$. In every iteration, node $n_{i, \ell}$ broadcasts $p_1, \dots, p_{|V_i|}$ values, each a tentative threshold value for a row in $Q_{i, \ell}$, using \fullref{wacc:tools:groupBroadcasting}, and in response, aggregates from the nodes of $N_{i, \ell}$, using \fullref{wacc:tools:groupBroadcasting} the total number of entries in each row of $Q_{i, \ell}$ below, equal to, and above the queried threshold. Each such iteration takes $\tilde O(|V_i|/c + 1) = \tilde O(n^{2/3}/c + 1)$ rounds, and after $\tilde O(1)$ iterations of this procedure, all the nodes in $N_{i, \ell}$ know a threshold for every row they posses, informing them which values in $Q_{i, n^{1/3}, \ell}$ can be thrown out.

Define the matrices $\hat P_{i, j, \ell}$ by removing from $P_{i, j, \ell}$ the entries which are thrown away due to the thresholds.\ \\

\noindent\textbf{Step: Balancing the Intermediate Representation}\ \\
The nodes computed the matrices $\hat P_{i, j, \ell}$, yet,
some matrices $\hat P_{i, j, \ell}$ may be too dense in order to transport out of the nodes which locally hold them. Even though we sparsified the matrices above, the sparsification steps perform were on several $\hat P_{i, j, \ell}$ matrices at once, and thus we can still have single $\hat P_{i, j, \ell}$ matrices which remains very dense. Let $\hat P_{x, y, z}$ be such a very dense matrix. We overcome this challenge by having more nodes compute $\hat P_{x, y, z}$ from scratch, allowing each node to only take responsibility for retaining a part of $\hat P_{x, y, z}$.

For each $i\in [n^{1/3}]$, we pool the nodes $U_i = \bigcup_{j \in [n^{1/3}]} U_{i, j}$ and redistribute them such that areas in the matrix which are too dense get more nodes.

Each node $\ell \in [n^{1/3}/2]$ from  $U_{i, j}$ computes the number of finite values in $\hat P_{i, j, \ell}$, denoted as $p_{i, j, \ell}$. Node $u_{i, j}$ computes $p_{i, j} = \sum_{\ell \in [n^{1/3}/2]} p_{i, j, \ell}$ using
on $U_{i, j}$ within $\tilde O(n^{1/3}/c + 1)$ rounds due to \fullref{wacc:tools:groupBroadcasting}. Finally, $u_{i, j}$ broadcasts to the other leader nodes $u_{i, 0}, \dots, u_{i, n^{1/3}}$ the values $p_{i, j, 0}, \dots, p_{i, j, n^{1/3}/2}$, and then broadcasts to $U_{i, j}$ all the $O(n^{2/3})$ values that it received -- taking $O(n^{2/3}/c + 1)$ rounds due to \fullref{wacc:tools:routing} and \fullref{wacc:tools:groupBroadcasting}.

Due to the fact that each row of $\hat P$ has at most $k$ elements in total, and currently $\hat P$ is distributed across $n^{1/3}/2$ matrices which need to be summed, all the nodes $U_i$ hold at most $k \cdot |V_i| \cdot n^{1/3}/2 \leq k \cdot n$ elements. That is, the sum $p_i = \sum_{j\in[n^{1/3}]}p_{i, j}$ is at most $k \cdot n$. Each node $\ell \in [n^{1/3}/2]$ from  $U_{i, j}$ observes $\hat P_{i, j, \ell}$ and locally breaks it up into $t(i, j, \ell) = \ceil{p_{i, j, \ell} / (2k \cdot n^{1/3})}$ matrices $\hat P_{i, j, \ell, 0}, \dots, \hat P_{i, j, \ell, t(i, j, \ell)}$ which sum up to $\hat P_{i, j, \ell}$ and each have at most $2k\cdot n^{1/3}$ finite elements. This creates at most $n^{2/3}$ such matrices. That is, $\sum_{j\in[n^{1/3}], \ell\in[n^{1/3}/2]} t(i, j, \ell) \leq \sum_{j\in[n^{1/3}], \ell\in[n^{1/3}/2]} \ceil{p_{i, j, \ell} / (2k \cdot n^{1/3})}  \leq  n^{2/3}$. Thus, the total number of intermediate matrices, spread over the nodes $U_i$, is at most $n^{2/3}$. Each $\ell \in [n^{1/3}/2]$ from $U_{i, j}$ is allocated $t(i, j, \ell) - 1$ other nodes from $U_i$, called \emph{auxiliary nodes} in order to send them the matrices $\hat P_{i, j, \ell, 1}, \dots, \hat P_{i, j, \ell, t(i, j, \ell)}$. Notice that since all nodes in $U_i$ know all the values $p_{i, j, \ell}$, all the nodes can locally know which node in $U_i$ is allocated to help which other node in $U_i$. However, node $\ell$ cannot send to all its auxiliary nodes all of this information, instead it sends to each of its auxiliary nodes the data it received from $S$ and $T$ with which it computed the matrix $P_{i, j, \ell}$, and the $O(n^{2/3})$ thresholds which it used to turn $P_{i, j, \ell}$ into $\hat P_{i, j, \ell}$. This can be accomplished via \fullref{wacc:tools:groupMulticasting} within $\tilde O(k \cdot n^{1/3}/c + n^{2/3}/c + 1)$ rounds, since each node wishes to multicast at most $\tilde O(k \cdot n^{1/3})$ data (as this is the bound on the total data each node received from $S$ and $T$), to at most $|U_i| = O(n^{2/3})$ other nodes, and each node desires to receive multicast messages only from one other node.\ \\

\noindent\textbf{Step: Summation}\ \\
We send data from $U_i$ to $V_i$ to perform the final summation step. Node $v \in V_i$ learns all of the information held in the nodes in $U_i$ which pertains to $\hat{P}[v]$.
All the nodes in $U_i$ know $Tokens(V_i)$, and vice versa and can thus communicate. Each node in $V_i$ wishes to receive $O(k \cdot n^{1/3})$ data from $U_i$, and likewise, every node in $U_i$  wishes to send $O(k \cdot n^{1/3})$ data. Thus, this communication is executed using \fullref{wacc:tools:routing} in $\tilde O(k \cdot n^{1/3} / c + 1)$ rounds. Upon receiving the data, each node $v \in V_i$ computes the at most smallest $k$ entries of $\hat P[v]$. Now, $\hat P$ is stored in a \emph{partial carrier configuration} (with every node $v$ having $C_v^{out} = \{v\}$), and thus we invoke \fullref{wacc:tools:transpose}, within $\tilde O(\sqrt{nk}/c + n/(k \cdot c) + 1)$ rounds, to ensure that $\hat P$ is stored in a carrier configuration $C$. Notice that $\tilde O(\sqrt{nk}/c + 1) = \tilde O(k \cdot n^{1/3}/c + n^{2/3}/c + 1)$, and so we are within the stated round complexity.
\end{proofof}
\section{Breaking Below \texorpdfstring{$o(n^{1/3})$}{n in 1/3} in  \ensuremath{\mathsf{Hybrid}}\xspace }\label{sec:subCubeRootAlgorithms}
We show a $(1+\varepsilon)$ approximation for weighted SSSP in the \ensuremath{\mathsf{Hybrid}}\xspace model within $\tilde O(n^{5/17}/\varepsilon^9)$ rounds, further implying that it is possible to compute a $(2+\varepsilon)$ approximation for the weighted diameter in this number of rounds.
We achieve this by combining a simulation of our \wacc model and of the \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace model. Roughly speaking, this incorporates \emph{density} awareness in addition to the \emph{sparsity} awareness discussed thus far.

A key approach in previous distance computations in the \ensuremath{\mathsf{Hybrid}}\xspace model~\cite{AHKSS20, kuhn2020computing,censorhillel2020distance} is to construct an overlay \emph{skeleton graph}, and show that solving distance problems on such skeleton graphs can be extended to solutions on the entire graph. In a nutshell, given a graph $G = (V, E)$ and some constant $0 < x < 1$, a \emph{skeleton graph} $S_x = (M, E_S)$ is generated by letting every node in $V$ independently join $M$ with probability $n^{x-1}$. Two skeleton nodes in $M$ have an edge in $E_S$ if there exists a path between them in $G$ of at most $\tilde O(n^{1-x})$ hops. 
In particular, the nodes of $S_x$ are \emph{well spaced} in the graph and satisfy a variety of useful properties. The central distance related property is that pair of far enough nodes in $G$ have skeleton nodes at \emph{predictable intervals} on some shortest path between them.

Given such a skeleton graph, $S_x = (M, E_s)$, with $|M| = \Theta(n^x)$, previous work showed that it is possible in the \ensuremath{\mathsf{Hybrid}}\xspace model to let the nodes in $M$ \emph{take control} over the other nodes in the graph and use \emph{all} the global bandwidth available to perform messaging between nodes in $M$. In essence, after $\tilde \Theta(n^{1-x})$ pre-processing rounds, the $\tilde \Theta(n)$ global bandwidth available to the \emph{entire} graph in each round of the \ensuremath{\mathsf{Hybrid}}\xspace model is utilized such that every node in $M$ can send and receive $\tilde \Theta (n/|M|) = \tilde \Theta (n^{1-x})$ messages per round from any other node in $M$, in an amortized manner.\footnote{In $\tilde \Theta(n^{1-x})$ rounds, each node in $M$ can send and receive $\tilde \Theta(n^{2-2x})$ messages to other nodes in $M$.} For a given $v \in M$, we denote by $H_v$ the set of \emph{helper} nodes of $v$ which contribute their globally communication capacity to $v$; it is guaranteed that all nodes in $H_v$ are at most $\tilde O(n^{1-x})$ hops away from $v$ in $G$.

A formal definition of skeleton graphs encapsulating all of the above, is in \cref{def:skeleton} in \cref{app:skelConst}.
These skeleton graphs are built upon nodes randomly selected from the input graph $G$, and thus the number of edges in $S_x$ correlates to the density of neighborhoods in $G$ -- the graph $S_x$ is either sparse or dense, depending on $G$. We split into cases according to the sparsity of $S_x$, which can be computed using known techniques from the \ensuremath{\mathsf{LOCAL}}\xspace and \ensuremath{\mathsf{Node\text{-}Capacitated\ Clique }}\xspace models.

\textbf{Sparse $S_x$:} A hurdle that stands in the way for going
below $o(n^{1/3})$ rounds is that one must choose $x>2/3$, in order for the $\tilde \Theta(n^{1-x})$-round pre-processing step to not exceed the goal complexity.
However, in order to use the previously shown routing techniques, the identifiers of the nodes in $M$ must be globally known, a task which can be shown to take $\tilde \Omega(n^{x/2}) = \omega (n^{1/3})$ rounds. This leads to an \emph{anonymity} issue -- letting nodes in $M$ communicate with one another although no node in the graph knows the identifiers of all the nodes in $M$.

We overcome this anonymity problem by showing a routing algorithm which allows messaging over $S_x$ without assuming that the identifiers of the nodes in $M$ are globally known. This allows us to simulate the \wacc model over $S_x$.
By simulating algorithms from the \wacc model on $S_x$, we directly get a $(1+\varepsilon)$-approximation for SSSP in $o(n^{1/3})$ rounds, with the exact round complexity dependent on the sparsity of $S_x$.
However, as $S_x$ approaches having $|M|^2 = \Theta(n^{2x})$ edges, the round complexity of the simulated \wacc model algorithms approaches $\tilde \Theta(n^{1/3})$. As such, using the techniques so far, we solve all cases except for \emph{very dense} skeleton graphs $S_x$.

\textbf{Dense $S_x$:} To tackle a \emph{dense} $S_x$, we present a \emph{density aware} simulation of the \ensuremath{\mathsf{BCC}}\xspace model over $S_x$. The \ensuremath{\mathsf{BCC}}\xspace model is simulated over $S_x$ in~\cite{AHKSS20} within $\tilde{O}(n^{1/3})$ rounds. Our observation is that as $S_x$ is more dense, broadcasting messages in the input graph can be made more efficient. In essence, as $S_x$ is more dense, neighborhoods in the original input graph $G$ are closely packed, and so when a node receives some message, it can efficiently share it with many nodes in its neighborhood. With this in hand, we can simulate the \ensuremath{\mathsf{BCC}}\xspace algorithm from \cite[Theorem 8]{Becker2017NearOptimalAS} for approximate SSSP very quickly on \emph{dense} skeleton graphs.

\textbf{Tying up the pieces:} Each simulation result by itself is insufficient, as in the extreme cases each solution takes $\tilde O(n^{1/3})$ rounds. Yet, by combining them and using each when it is better, based on the sparsity of $S_x$, we achieve the resulting $\tilde O(n^{5/17}) = o(n^{1/3})$ round algorithm, for all graphs.


~\\
The outline of the rest of this section:
We first perform routing over skeleton graphs where the receivers of messages do not know which nodes desire to send them messages (\Cref{subsec:routingHybrid}). In \Cref{subsec:simHybrid}, we simulate the \wacc model in the \ensuremath{\mathsf{Hybrid}}\xspace model. Next, we state that the \ensuremath{\mathsf{BCC}}\xspace model can be simulated in the the \ensuremath{\mathsf{Hybrid}}\xspace model, and defer the proof to \cref{app:littleO}.
Finally, in \Cref{subsec:SSSPHybrid}, we combine our various algorithms to yield the SSSP approximation result from which the weighted diameter approximation result also follows.

\subsection{Oblivious Token Routing}
\label{subsec:routingHybrid}

The following claim shows how to route unicast messages inside a skeleton graph, and is based on \fullref{thr:tokenRouting} shown in \Cref{app:ObliviousTR}. 

\begin{restatable}[Skeleton Unicast]{claim}{SklUnicast}\label{skeletons:unicast}
Given a graph $G$, a skeleton graph $S_x=(M, E_S)$, and a set of messages between the nodes of $M$, s.t. each $v \in M$ is the sender and receiver of at most $k = \tilde O(n^{2-2x})$ messages, and each message is initially known to its sender, it is possible to route all given messages within $\tilde O(n^{1-x})$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model.
\end{restatable}


\fullref{skeletons:unicast} is an extremely important requirement for showing our $o(n^{1/3})$ round algorithms. Previously, \cite{kuhn2020computing} required that every node knows how many messages every other node intends to send to it. In turn, this would require that for each $v \in M$, all the other nodes in $M$ know the identifier of $v$. But the latter can be shown to take $\omega(n^{x/2}) = \omega(n^{1/3})$ rounds, since $x > 2/3$ (as elaborated above). Therefore, the necessity of our strengthened claim follows. 



\subsection{\texorpdfstring{\wacc}{AC(c)} and \ensuremath{\mathsf{BCC}}\xspace Simulations in \ensuremath{\mathsf{Hybrid}}\xspace}
\label{subsec:simHybrid}
\begin{restatable}[\wacc Simulation in  \ensuremath{\mathsf{Hybrid}}\xspace]{theorem}{WaccSim}
\label{claim:wacc:simulation}
    Consider a graph $G=(V, E)$, and a skeleton graph $S_x=(M, E_S)$ of $G$, for some \emph{constant} $2/3 < x < 1$. Let $ALG_{AC}$ be an algorithm which runs in the \wacc model with capacity $c=\tildeTheta{n^{2-2x}}$ over $S_x$ in $t$ rounds. Then there exists an algorithm which simulates $ALG_{AC}$ within $\tildeTheta{t \cdot n^{1-x}}$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model over $G$, \whp Further, it is ensured that at the start of the simulation, every node in $M$ knows the \emph{communication tokens} of all its neighbors in $S_x$.
\end{restatable}

\begin{proofof}{\cref{claim:wacc:simulation}}We show that we can instantiate the \wacc model over $S_x$ and then show how to simulate each round.

In order to instantiate the \wacc model over the nodes $M$, the \wacc model definition asserts that every node $v \in M$ has an identifier in $[|M|]$ as well as a communication token whose knowledge enables other nodes to communicate with $v$. In order to ensure the condition related to identifiers is satisfied, we invoke \fullref{hybrid:treeConstruction} over $G$ and $S_x$ in $\tilde O(1)$ rounds. For the second condition, each node $v \in M$ uses its original identifier in the \ensuremath{\mathsf{Hybrid}}\xspace model as its communication token in the \wacc model, which enables us to use \fullref{skeletons:unicast} in order to later simulate the rounds of the \wacc model. Finally, notice that it holds that every node in $M$ knows the communication tokens of all its neighbors in $S_x$, as the communication tokens are the \ensuremath{\mathsf{Hybrid}}\xspace model identifiers.


In each round of the \wacc model, each node sends/receives at most $c$ messages to/from any other node, such that for each message it either knows the communication token of the recipient or the recipient is chosen independently, uniformly at random. We split each round of the \wacc model into two phases. First, we route the messages which use communication tokens, and second, we route those messages destined to random nodes. Since the communication tokens in the \wacc model are the identifiers from the \ensuremath{\mathsf{Hybrid}}\xspace model, the first phase is implemented straightforwardly using \fullref{skeletons:unicast}, taking $\tildeBigO{n^{1-x}}$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model over $G$, as required.

For the second phase, denote by $R_v$ the messages which node $v$ desires to send to random targets. Node $v$ selects, uniformly and independently, $|R_v| \leq c$ random nodes from $G$, where each node is the target for a different message in $R_v$ -- from here on, we assume that a message in $R_v$ has the identifier of a random node in $G$ attached to it. For each helper $u \in H_v$, node $v$ assigns $c / |H_v| = \tilde O(n^{1-x})$ messages from $R_v$, denoted by $R_v^u$, to $u$. Within $\tilde O(n^{1-x})$ rounds, node $v$ uses the local edges of the \ensuremath{\mathsf{Hybrid}}\xspace model in order to inform $u \in H_v$ about $R_v^u$. Next, each node $u$ uses the global edges of the \ensuremath{\mathsf{Hybrid}}\xspace model in order to send the messages $R_v^u$ to their targets in $G$, within $\tilde O(n^{1-x})$ rounds, due to \fullref{thr:sendingToUniform}. Finally, given that a node $u\in V$ received a message in this way, node $u$ selects uniformly and independently at random a node such that $u \in H_v$ and forwards that message $v$. Notice that it can be the case that a certain $u \in V$ does \emph{not} help any node, and thus there does \emph{not} exist a node $v \in M$ such that $u \in H_v$ -- in such a case, $u$ will report back to whichever node sent it the message saying that it cannot forward it. However, the definition of a skeleton graph promises that the total number of helper nodes of nodes in $M$ is at least $\tilde\Omega{(n)}$ (Property~\ref{itm:helper:many} of \fullref{def:skeleton}). As every node assists at most $\tilde O(1)$ other nodes, this implies that at least a poly-logarithmic fraction of the nodes assist other nodes, and so if we repeat the above process and resend messages that \emph{bounced back}, within $\tilde O(1)$ iterations of the above algorithm, \whp, all messages are forwarded.

Notice that the above methodology does not produce a uniform distribution of receivers over the nodes $M$, since there might be some node $v \in M$ such that all of $H_v$ \emph{only} help $v$, and a node $u \in M$ such that all the nodes $H_u$ also help other nodes in $M$ (thus $u$ is less likely than $v$ to receive a random message). This happens even though each node only helps at most $\tilde O(1)$ other nodes and the number of nodes in $H_v$ is \emph{exactly the same} for each $v \in M$. Thus, we augment the probabilities with which a node $v \in M$ \emph{accepts} a message. Each node $v \in M$ observes its helpers $H_v$ and computes the probability, denoted $p_v$, that given that a uniformly chosen node $u \in H_v$ received a message, $u$ forwards the message to $v$. Now, the nodes $M$ utilize an Aggregate and Broadcast tool of~\cite[Theorem 2.2]{AGGHKL19} (see \fullref{thr:aggregateAndBroadcast}) in order to compute $p = \min_{v\in M}p_v$. Every node $v \in M$ now \emph{accepts} each message it received with probability $p/p_v$, independently. In the case that a node $v \in M$ rejects a message, it notifies the original sender of the message that the message was rejected -- this is done by sending messages in the reverse direction to the way they were sent previously. In the case that a node $v \in M$ hears that a message it sent was rejected, it will attempt to resend it by repeating the entire algorithm above. As every node $u \in V$ helps at most $\tilde O(1)$ nodes $v \in M$, it holds that $p = \tilde \Omega(1)$, and so within $\tilde O(1)$ iterations of the above algorithm, \whp, every message will be successfully delivered.
\end{proofof}

The following is proven in \Cref{app:littleO}.
\begin{restatable}[\ensuremath{\mathsf{BCC}}\xspace Simulation in \ensuremath{\mathsf{Hybrid}}\xspace]{theorem}{BCCSim}
\label{thr:bccInHybrid}
    Given a graph $G=(V, E)$, a skeleton graph $S_x=(M, E_S)$, for some \emph{constant} $2/3 < x < 1$, with average degree $k = \Theta(|E_S|/|M|)$, and an algorithm $ALG_{BCC}$ in the \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace model which runs on $S_x$ in $t$ rounds, it is possible to simulate $ALG_{BCC}$ by executing $\tilde O(t \cdot (n^{2x-1}/\sqrt{k} + n^{1-x}))$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model on $G$. This assumes that prior to running $ALG_{BCC}$, each node $v \in S_x$ has at most $\tilde O(\deg_G(v))$ bits of input used in $ALG_{BCC}$, including, potentially, the incident edges of $v$ in $S_x$, and that the output of each node in $ALG_{BCC}$ is at most $O(t \log n)$ bits. 
\end{restatable}


\subsection{A \texorpdfstring{$(1+\varepsilon)$}{1+epsilon}-Approximation for SSSP}
\label{subsec:SSSPHybrid}
We show an $\tilde O(n^{5/17}/\varepsilon^9)$ round algorithm for a $(1+\varepsilon)$-approximation of weighted SSSP in the \ensuremath{\mathsf{Hybrid}}\xspace model. We begin by showing how to use the \wacc algorithm from \fullref{theorem:wacc:approxSSSP} in the \ensuremath{\mathsf{Hybrid}}\xspace model for sparse skeleton graphs, with low maximal degree and even lower average degree, we then show an algorithm in the \ensuremath{\mathsf{Hybrid}}\xspace model for graphs with low average degree, yet high maximal degree, and then finally we show how to use the \ensuremath{\mathsf{Broadcast\ Congested\ Clique}}\xspace algorithm from \cite[Theorem 8]{Becker2017NearOptimalAS} in the \ensuremath{\mathsf{Hybrid}}\xspace model for dense graphs, with high average degree. Combining these claims using \fullref{theorem:approxSSSP} gives the desired result.




\begin{lemma}[SSSP with Low Average and Maximal Degrees]
\label{theorem:hybrid:approxSSSP:wacc}
Given a \emph{weighted} input graph $G = (V, E)$, and a skeleton graph $S_x=(M, E_S)$, s.t. the average and maximal degrees in $S_x$ are $k = \tilde O(n^{x/2})$ and $\Delta_{S_x} = O(n^{2-2x})$, respectively, a value $0 < \varepsilon < 1$, and a source node $s \in M$, ensures that every node in $M$ knows a $(1+\varepsilon)$-approximation to its distance from $s$ over the edges $E_S$, within $\tilde O((n^{11x/6 - 1} + n^{1-x})/\varepsilon)$ rounds in the \ensuremath{\mathsf{Hybrid}}\xspace model, \whp
\end{lemma}

\begin{proofof}{\cref{theorem:hybrid:approxSSSP:wacc}}
    Use \fullref{claim:wacc:simulation} to simulate in the \ensuremath{\mathsf{Hybrid}}\xspace model over $G$ the SSSP algorithm from \fullref{theorem:wacc:approxSSSP} over $S_x$. Set capacity $c = \tilde \Theta(n^{2-2x})$ for a round complexity  of 
    $\tilde O(n^{1-x} \cdot (((n^x)^{5/6} + k \cdot (n^x)^{1/3})/(c\cdot \varepsilon) + 1/\varepsilon + \Delta_{S_x}/c)) = \tilde O(n^{1-x} \cdot (((n^x)^{5/6} + n^{x/2} \cdot (n^x)^{1/3})/(c\cdot \varepsilon) + 1/\varepsilon + \Delta_{S_x}/c)) = \tilde O((n^{5x/6 - 2 + 2x + 1 - x} + n^{1-x})/\varepsilon + \Delta_{S_x} / n^{1-x} ) = \tilde O((n^{11x/6 - 1} + n^{1-x})/\varepsilon)$.\end{proofof}

\fullref{theorem:wacc:approxSSSP} depends on the maximal degree, and so applying it to a skeleton graph with high maximal degree is inefficient. Thus, for sparse skeleton graphs with a high maximal degree, we show a \ensuremath{\mathsf{Hybrid}}\xspace algorithm ensuring one node in the skeleton graph can learn all of the skeleton graph and inform the nodes of their desired outputs. The proof of the following appears in \Cref{app:littleO}.

\begin{restatable}[SSSP with Low Average and High Maximal Degrees]{lemma}{SSSPLAHM}
\label{theorem:hybrid:approxSSSP:highMaximalDegree}
Given a \emph{weighted} input graph $G = (V, E)$, and a skeleton graph $S_x=(M, E_S)$, for some \emph{constant} $2/3 < x \leq 12/17$, such that the average and maximal degrees in $S_x$ are at most $\tilde O(n^{x/2})$ and at least $\Delta_{S_x} = \omega(n^{2-2x})$, respectively, and a source node $s \in M$, ensures that every node in $M$ knows its distance from $s$ over the edges $E_S$, within $\tilde O(n^{1-x})$ rounds in the \ensuremath{\mathsf{Hybrid}}\xspace model, \whp

\end{restatable}

We use our efficient \ensuremath{\mathsf{BCC}}\xspace simulation for \emph{dense} skeleton graphs.

\begin{lemma}[SSSP with High Average Degree]
\label{thr:ssspByBccInHybrid}
    Given a weighted, undirected input graph $G = (V, E)$, a skeleton graph $S_x=(M, E_S)$, for some \emph{constant} $2/3 < x < 1$, such that the average degree in $S_x$ is at least $k=\tildeBigOmega{n^{x/2}}$, a value $0 < \varepsilon < 1$, and a source node $s\in M$, ensures that every node in $M$ knows a $(1+\varepsilon)$-approximation to its distance from $s$ over the edges $E_S$, within  $\tildeBigO{(n^{7x/4-1} + n^{1-x})/\varepsilon^9}$ rounds in the \ensuremath{\mathsf{Hybrid}}\xspace model, \whp
\end{lemma}
\begin{proofof}{\cref{thr:ssspByBccInHybrid}}
    \fullref{thr:bccInHybrid} simulates the SSSP approximation algorithm of \cite[Theorem 8]{Becker2017NearOptimalAS} on $S_x$. As the complexity of \cite[Theorem 8]{Becker2017NearOptimalAS} is $\tilde O(\varepsilon^{-9})$ rounds of the \ensuremath{\mathsf{BCC}}\xspace model, the simulation takes $\tilde O(\varepsilon^{-9} \cdot (n^{2x-1}/\sqrt{k} + n^{1-x})) = \tilde O(\varepsilon^{-9} \cdot (n^{2x-1 - (x/2)/2} + n^{1-x})) =  \tildeBigO{(n^{7x/4-1} + n^{1-x})/\varepsilon^9}$ rounds of the \ensuremath{\mathsf{Hybrid}}\xspace model.
\end{proofof}

Finally, we combine \fullref{theorem:hybrid:approxSSSP:wacc,theorem:hybrid:approxSSSP:highMaximalDegree,thr:ssspByBccInHybrid}.


\approxSSSP*

\begin{proofof}{\cref{theorem:approxSSSP}}
    Denote $x=12/17$. Construct a skeleton graph $S_x=(M, E_S)$ in $\tilde O{(n^{1-x})} = \tilde O(n^{5/17})$ rounds using \fullref{claim:skeleton}. Notice that \fullref{claim:skeleton} can ensure that source $s$ is also in $M$. Using \fullref{thr:aggregateAndBroadcast}, compute $k = \Theta(|E_S|/|M|)$ and the maximal degree in $S_x$, the value $\Delta_{S_x}$, in $\tilde O(1)$ rounds.
    
    First, ensure every node in $S_x$ knows a $(1+\varepsilon)$-approximation to its distance from $s$ over the edge set $E_S$ only. Thus, selectively deploy \cref{thr:ssspByBccInHybrid,theorem:hybrid:approxSSSP:wacc,theorem:hybrid:approxSSSP:highMaximalDegree}, as follows. If $k = \tilde \Omega(n^{x/2})$, invoke \cref{thr:ssspByBccInHybrid} in $\tildeBigO{(n^{7x/4-1} + n^{1-x})/\varepsilon^9} = \tildeBigO{(n^{(7/4)\cdot(12/17)-1} + n^{1-12/17})/\varepsilon^9} = \tildeBigO{(n^{4/17} + n^{5/17})/\varepsilon^9} = \tildeBigO{n^{5/17}/\varepsilon^9}$ rounds. Otherwise, $k= O(n^{x/2})$, and so split the algorithm into two cases, according to $\Delta_{S_x}$. If $\Delta_{S_x} = O(n^{2-2x})$, invoke \cref{theorem:hybrid:approxSSSP:wacc}, in $\tilde O((n^{11x/6 - 1} + n^{1-x})/\varepsilon) = \tilde O((n^{(11/6) \cdot (12/17) - 1} + n^{1-12/17})/\varepsilon) = \tildeBigO{n^{5/17}/\varepsilon}$ rounds, and otherwise invoke \cref{theorem:hybrid:approxSSSP:highMaximalDegree} in $\tilde O(n^{1-x}) = \tildeBigO{n^{5/17}}$ rounds.
    
    Finally, due to Property~\ref{itm:skeleton:distance} of the definition of a skeleton graph, we invoke \fullref{thr:computeMSSPFromMSSPOnSkeleton}, in $\tilde O(n^{5/17})$ rounds, to ensure every $v \in V$ knows a $(1+\varepsilon)$-approximation to its distance from $s$ in $G$.
\end{proofof}

\fullref{theorem:approxSSSP} with $\alpha=1+\varepsilon/2$ and \fullref{thr:ssspToDiameter} give the following.
\begin{restatable}[$(2+\varepsilon)$-Approximation for Weighted Diameter in \ensuremath{\mathsf{Hybrid}}\xspace]{theorem}{HybridWeightedDiameter}\label{thr:weightedDiameter2PlusEps}
    It is possible to compute a $(2+\varepsilon)$-approximation for weighted diameter in $\tilde O(n^{5/17}/\varepsilon^9)$ rounds in the \ensuremath{\mathsf{Hybrid}}\xspace model, \whp
\end{restatable}

\section{Fast Distance Computations in the \ensuremath{\mathsf{CONGEST}}\xspace Model}\label{sec:congest}
In \Cref{subsec:simCongest} we show how to simulate the \wacc model in \ensuremath{\mathsf{CONGEST}}\xspace.
We then employ our simulation to simulate the \ensuremath{\mathsf{Congested\ Clique}}\xspace model in \ensuremath{\mathsf{CONGEST}}\xspace (\Cref{subsec:CCsimCongest}), and to derive our distance computations in \ensuremath{\mathsf{CONGEST}}\xspace (\Cref{subsec:distancesCongest}).

\subsection{\texorpdfstring{\wacc}{AC(c)} Simulation in \ensuremath{\mathsf{CONGEST}}\xspace}
\label{subsec:simCongest}

\noindent\textbf{Key Principle.}
In the \ensuremath{\mathsf{CONGEST}}\xspace model, each node $v$ can send or receive $\deg_G{(v)}$ messages in each round, implying a total bandwidth of $2m$ messages per round. We aim to build efficient distance tools which utilize this bandwidth \emph{completely}. Consider the \wacc[m/n] model, which also has a bandwidth of $2m$ messages per round. Potentially, by comparing the bandwidths, it could be possible to simulate one round of the \wacc model in single round of the \ensuremath{\mathsf{CONGEST}}\xspace model. However, in the \ensuremath{\mathsf{CONGEST}}\xspace model, nodes with degree $\littleO{m / n}$ can not send $m / n$ messages in a single round, regardless of how an algorithm tries to do this. 

To overcome this problem, we notice that the bandwidth of the nodes with degree at least $m / (4n)$ is at least $7m / 4$. Thus, the key principle we show is that the high degree nodes, denoted by $H$, can \emph{learn} all of the input of the low degree nodes, denote by $L$. The higher the degree of a node, the more nodes it simulates. Formally, we create an assignment $\rho \colon L\mapsto H$ where for every $\ell \in L$, the node $\rho(\ell)\in H$ simulates $\ell$, and we ensure that $\rho$ is \emph{globally known}.

We then simulate the \wacc[m/n] model using only the nodes in $H$, and finally we send back the resulting output to the nodes in $L$. To allow all-to-all communication between the nodes in $H$, we use the routing algorithms developed in \cite{Ghaffari2017DistributedMA,Chang2019DistributedTD} and stated in \cref{app:congest} and pay an overhead of $\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds for the simulation.







Some problems, such as Scattered APSP, require the output to be stored on some node, but do not specify on which. We adapt for this case by allowing nodes to produce an \emph{auxiliary output}. After the simulation is over, every node $u$, given the communication token of any node $v$  can compute the identifier of node $w$ where the auxiliary output of $v$ is stored.

~\\
\noindent\textbf{Carrier Configuration and Communication Tokens.}
In addition to simulating the \wacc model in the \ensuremath{\mathsf{CONGEST}}\xspace model, we let every node know the communication token of its neighbors as well as construct a carrier configuration directly in the \ensuremath{\mathsf{CONGEST}}\xspace model. This benefits some graph problems greatly.

Note that in the simulation in the \ensuremath{\mathsf{Hybrid}}\xspace model, the carrier configuration is constructed in the \wacc model itself. However, in the case of the \ensuremath{\mathsf{CONGEST}}\xspace model, we cannot delegate this task efficiently to the \wacc model since building a carrier configuration requires every node to be able to send its incident edges to arbitrary nodes in the graph. Doing so takes $\Omega(\Delta \cdot n/m)$ rounds in the \wacc[m/n] model, yet only $O(\tau_{\text{mix}} \cdot n^{o(1)})$ rounds in \ensuremath{\mathsf{CONGEST}}\xspace.

However, building a carrier configuration in the \ensuremath{\mathsf{CONGEST}}\xspace model is also not directly possible, as a low degree carrier might learn $\bigOmega{m / n}$ edges of other nodes, which could take $\bigOmega{m / n}$ rounds. Therefore, instead of each node sending its edges directly to its carriers, it sends them to the nodes which simulate its carriers.



Overall this might sound like a back and forth process, as we simulate low degree nodes by high degree nodes and then split the edges of the high degree nodes among nodes which may be simulated nodes. 
However, using the \wacc model grants us the modular approach we aim for.


~\\
\noindent\textbf{Supergraphs.}
\fullref{theorem:wacc:hopsets} constructs hopsets and \cref{theorem:wacc:approxAPSP} computes Scattered APSP in the \wacc model, and both require the input graph to have $\bigOmega{n^{3/2}}$ edges.\footnote{This assumption can be removed at the expense of more complicated proofs, yet would not imply any speed-up for our end-results.} We aim to apply those results on general graphs and so augment $G$ with $\bigO{n}$ added nodes and $\bigTheta{n^{3/2}}$ added edges 
while preserving distances between the nodes of $V$ and ensuring that all added edges are globally known. We call the resulting graph $G'$ an \emph{$n^{3/2}$-supergraph}, build a carrier configuration holding $G'$, and apply the \wacc algorithms on $G'$.




\begin{definition}
    Given a weighted graph $G=(V, E, w)$ with $n=\size{V}$ and $m=\size{E}$, and a number $0\leq m'\leq n^2$, a weighted graph $G'=(V', E', w')$ is an $m'$-\emph{supergraph} of $G$, if $G'=(V', E', w')$ is obtained from $G$ by adding $\ceil{m' / n}$ new nodes and adding an infinite weight edge between every added node and every original node. 
\end{definition}

Clearly, a supergraph preserves the original distances.




We now simulate the \wacc model in the \ensuremath{\mathsf{CONGEST}}\xspace model.

\begin{restatable}[\wacc Simulation in \ensuremath{\mathsf{CONGEST}}\xspace]{theorem}{hcWACCSimulation}\label{lemma:hc:waccSimulation}
    Consider a graph $G$ and some constant $c$. Let $m'$ be some number s.t. $0\leq m'\leq n^2$.
    Let $k=m/n$ be the average degree of $G$ and let $A$ be an algorithm which runs in the \wacc model over $G$ in $t$ rounds. For each $v$ denote by $i_v\log{n}$ and $o_v\log{n}$ the number of bits in the input and output of the node $v$, respectively. Let $i_c=\max_{v\in V}\set{1 + i_v/\deg_G(v)}$ and $o_c=\max_{v\in V}\set{1 + {o_v/\deg_G(v)}}$ be the input and output \emph{capacities}: the minimum number of rounds required for any node to send or receive its input or output, respectively.
    
    There exists an algorithm which simulates $A$ within $(m'/m + i_c + \ceil{c/k}\cdot t + o_c)\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds of the \ensuremath{\mathsf{CONGEST}}\xspace model over $G$. 
    The above works even if $A$ requires a carrier configuration of $G'$ (an $m'$-supergraph of $G$) or communication tokens of neighbors as an input.
    Furthermore, each node $u$ might produce some unbounded auxiliary output, in which case the output is known to some (not necessary same) node $v$ such that each node $w$ can compute the identifier of $v$ given the communication token of $u$.

\end{restatable}


\begin{proofof}{\cref{lemma:hc:waccSimulation}}

\textbf{Identifiers:}
    First, compute $k=m/n$ in $O(D) = O(\tau_{\text{mix}})$ rounds.
    By the definition of the \ensuremath{\mathsf{CONGEST}}\xspace model, each node $v$ has an identifier $v\in\interval{n}$, denoted the \emph{original} identifier. Use \fullref{cor:hc:identifiers}, to compute a set of \emph{new} identifiers $ID_{new}\colon V\mapsto \interval{n}$. We abuse notation and denote by $\deg_G(i)$ the degree of node $v$ with identifier $ID_{new}(v)=i$. Each node $v$ locally computes for each new identifier $i\in \interval{n}$ its value $\floor{\log\deg_G{(i)}}$. A node $v\in V$ with degree that is less than $2^{\floor{\log{k}}-2}$ is a \emph{low} degree node $v\in L$, otherwise it is a \emph{high} degree node $v\in H$. According to the properties of $ID_{new}$, the new identifiers of nodes in $L$ are smaller than those of nodes in $H$. We abuse the notation and treat $L$ and $H$ as set of new identifiers.
    For each $i\in L$ denote $x_i=\floor{\log\deg_G{(i)}}$ and for each $j\in H$ denote $y_j=\floor{\log\deg_G{(i)}}$. 
    
    \textbf{Simulation Assignment:} The numbers $\size{L}, \size{H}$ and the sets $\set{x_i}_{i\in L}, \set{y_j}_{j\in H}$ satisfy the conditions of \fullref{lemma:hc:assignment}, since $\sum_{i\in L}{2^{x_i}} + \sum_{j\in H}{2^{y_j}}=\sum_{v\in V}{2^{\floor{\deg_G{(v)}}}}>\sum_{v\in V}{2^{\deg_G{(v)} - 1}}=2m/2=m$. 
    Hence, there is a partition of $L$ into $\size{H}$ sets $\set{I_j}$, satisfying $\size{I_j}\leq 4\cdot \floor{2^{y_j}/k}\leq 4\floor{\deg_G{(v)}/k}$. The node $j\in H$ simulates the nodes in $I_j$, and for simplicity it also simulates itself. Denote by $\rho(i)$ the new identifier of the node simulating the node with new identifier $i$.
    
    \textbf{Input:} For every $j \in H$, we now deliver the information node $j$ requires to simulate nodes in $I_j$. Each $u$ sends to its neighbors its new identifier $ID_{new}(u)$. As $u$ knows its new identifier $ID_{new}(u)$, it also knows the new identifier of $j$. Using \fullref{claim:hc:routing}, $u\in L$ sends to the node $\rho(u)$ its new and original identifier together with the new and original identifiers of its neighbors and input.
    A node $v\in H$, for each neighbor $w$ of node $u\in I_{v}$,can now locally compute the new identifier of $\rho(w)$.
    This invokes the algorithm from \fullref{claim:hc:routing} at most $\bigO{i_c}$ times. In each invocation, each $u\in L$ sends at most $\deg_G(u)$ messages and each node $v\in H$ receives at most $4\cdot (\deg_G(v)/k)\cdot k=\deg_G(v)\cdot 2^{\bigO{\sqrtlgn}}$ messages, as required.
    \textbf{Instantiation:} We now instantiate the \wacc model. As a communication token of node $v$ in the \wacc model, we use the concatenation of $v$, $\rho(v)$ and $ID_{new}(v)$. Clearly, identifiers are unique in $\interval{n}$ and communication tokens are unique of size $\bigO{\log{n}}$ bits. While pre-possessing, we already guaranteed that the node which simulates $u$ knows the communication token of all neighbors of $u$.
    %
    Now the new identifier assignment $ID_{new}$ and simulation assignment $\rho$ satisfy the demands of \fullref{lemma:hc:waccSimulation:carrierConfiguration} and we use it to build carrier configuration.
    
    \textbf{Round Simulation:} During one round of the \wacc model, each node can send and receive at most $c$ messages. Each message is sent either to a random node or a node with a known communication token. We split into two phases. First, sending the messages to nodes with known communication tokens, and second sending the messages to random nodes.
    
    In the first phase, we use the fact that the new identifier of the destination is a part of the communication token. Each node $v\in H$ has to send and receive messages on behalf of all $I_v$. Thus, node $v\in H$ has to send and receive at most $(4\cdot \floor{\deg{(v)}/k} + 1)\cdot c\leq (4\cdot\deg{(v)}+1)\ceil{c/k}$ messages. It is therefore enough to invoke the algorithm from \fullref{claim:hc:routing} for $\tildeBigO{\ceil{c/k}}$ times to deliver all the messages \whp.
    
    In the second phase, for each message, we chose a new identifier independently and uniformly. Since for node $u$ we know the new identifier of $\rho(u)$, we also know where to route the message to. As $n$ nodes sample uniformly at most $c$ messages, each new identifier is sampled at most $\tildeBigO{c}$ times, \whp. Thus, the number of messages that a high degree node $v\in H$ has to send or receive is at most $\tildeBigO{\deg{(v)}c/k}$. Thus, \whp, $\tildeBigO{\ceil{{c/k}}}$ invocations of algorithm from \fullref{claim:hc:routing} suffice.
    
    \textbf{Main Output:} Finally, we send outputs back to the simulated nodes. This works in a similar manner, with a node $v\in H$ splitting the output of each node $u\in I_{v}$ into $\ceil{{o_u/\deg{(u)}}}$ batches of size at most $\deg{(u)}$. Notice that since $v$ receives the identifiers of all neighbors of $u$, it knows $\deg{(u)}$. Then, for $o_c$ rounds, each node uses \fullref{claim:hc:routing} to send one batch to each node it simulates.
    
    \textbf{Auxiliary Output:} The auxiliary output that some node $u$ produces is stored in the node $v=\rho(u)$ which simulates it. Since $\rho(u)=v$ is a part of the communication token of $u$, each node $w$ which knows the communication token of $u$, knows also $v$.
    

    \textbf{Round Complexity:} By \fullref{cor:hc:identifiers}, computing new identifiers takes $\bigO{\tau_{\text{mix}} + \log{n}}$ rounds. 
    By \fullref{claim:hc:routing}, sending the input requires $i_c\cdot \ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, the simulation of the $t$ rounds of the \wacc model requires $\ceil{\frac{c}{k}}\cdot t \cdot \ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, and sending the output back takes $o_c\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp By \fullref{lemma:hc:waccSimulation:carrierConfiguration}, building the carrier configuration takes $\ceil{m'/m}\ensuremath{\tmix\cdot \twosqlgnlglgn} $ rounds \whp. Thus, the execution terminates in $(m'/m + i_c + \ceil{c/k}\cdot t + o_c)\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp.
\end{proofof}


\subsection{Faster \ensuremath{\mathsf{Congested\ Clique}}\xspace Simulation}
\label{subsec:CCsimCongest}


The \wacc model is, in a sense, a generalization of the \ensuremath{\mathsf{Congested\ Clique}}\xspace model, directly implying the following.




\begin{claim}[\ensuremath{\mathsf{Congested\ Clique}}\xspace Simulation in \wacc]\label{lemma:wacc:clique}
There is an algorithm, which executes one round of the \ensuremath{\mathsf{Congested\ Clique}}\xspace model in the \wacc[c] in $\tildeBigO{\frac{n}{c}}$ rounds \whp 
\end{claim}
\begin{proofof}{\cref{lemma:wacc:clique}}
    Initially, for $\tildeBigO{\frac{n}{c}}$ rounds, each node sends its communication token and identifier to $c$ (not necessary distinct) randomly sampled nodes. By Chernoff and union bounds, all nodes receive the identifiers and communication tokens of all other nodes \whp
    For an additional $\tildeBigO{\frac{n}{c}}$ rounds, the nodes use the learned communication tokens to deliver the messages they have.
\end{proofof}

Combining \fullref{lemma:wacc:clique,lemma:hc:waccSimulation} implies a \emph{density aware} simulation of the \ensuremath{\mathsf{Congested\ Clique}}\xspace model in the \ensuremath{\mathsf{CONGEST}}\xspace model -- the more edges the input graph has, the faster the simulation.


\begin{reptheorem}{cor:hc:cliqueSimulation}[\ensuremath{\mathsf{Congested\ Clique}}\xspace Simulation in \ensuremath{\mathsf{CONGEST}}\xspace]Consider a graph $G=(V, E)$, and $A$ an algorithm which runs in the \ensuremath{\mathsf{Congested\ Clique}}\xspace model over $G$ in $t$ rounds. For each $v$ denote by $i_v\log{n}$ and $o_v\log{n}$ its number of input and output bits, respectively. Let $i_c=\max_{v\in V}\set{1 + i_v/\deg_G(v)}$ and $o_c=\max_{v\in V}\set{1 + {o_v/\deg_G(v)}}$ be the input and output \emph{capacities}: rounds required for any node to send or receive its input or output, respectively.
    Then $A$ can be simulated within $(i_c + {{n^2}/{m}}\cdot t + o_c)\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds of the \ensuremath{\mathsf{CONGEST}}\xspace model over $G$, \whp.
\end{reptheorem}










\subsection{Improved Distance Computations}
\label{subsec:distancesCongest}

We show an exact SSSP algorithm via a simulation of the algorithm from \fullref{lemma:hc:waccSimulation}.
\exactSSSPInHC*
\begin{proofof}{\cref{theorem:hc:exactSSSP}}
    The claim follows from simulating \fullref{theorem:wacc:exactSSSP} of \wacc[m/n] over $G$ using \fullref{lemma:hc:waccSimulation}, in $ (1 + \tilde O(m^{1/2}n^{1/6}/c + n/c + n^{7/6}/m^{1/2})\cdot\ceil{c / k})\ensuremath{\tmix\cdot \twosqlgnlglgn}={(n^{7/6}/m^{1/2} + n^2/m)}\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp
\end{proofof}






Now, we define and approximate our first APSP relaxation.

\begin{definition}[Shortest Path Query Problem]\label{def:SPquery}
Given an input graph $G$, a \emph{query set} is a set of $q$ source-destination pairs $Q=\set{(s_i, t_i)}_{i=1}^{q}$ called \emph{queries}.
For each node $u$, the \emph{source and 
destination loads}, $u_s$ and $u_t$, respectively, are the number of times $u$ appears as a source and destination in $S$ divided by its degree. The maximum $\ell$ over all source and destination loads is the query set \emph{load}.

A \emph{shortest path query problem} is a query set of size $q$ and load $\ell$, s.t. every
$s_i$ knows the identifier of
$t_i$. The goal is to answer all queries, that is,
$s_i$ computes or approximates $d_G(s_i, t_i)$.

Given an input graph $G$, an algorithm is a \emph{shortest path query algorithm} if, after some pre-processing of $T_{pre-processing}$ rounds, given any query set of size $q$ and load $\ell$, the algorithm solves shortest path query problem within an additional number of $T_{query}$ rounds.
\end{definition}

We follow the approach of \cite{SparseMMPODC2019} in order to design a $(3+\varepsilon)$-approximate shortest path query algorithm, using our methods from the \wacc model. For this we use the following important tool whose proof deferred to \cref{app:hc:knearest}.


\begin{restatable}[$k$\textsc{-nearest}\xspace in \ensuremath{\mathsf{CONGEST}}\xspace]{lemma}{hcKnearest}\label{claim:hc:knearest}
    Given a graph $G$, it is possible in the \ensuremath{\mathsf{CONGEST}}\xspace model, within ${(k \cdot n^{4/3}/m + n^{5/3}/m + 1)}\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp, to compute the distance $d_G(v, u)$ from every node $v$ to every node $u$ which is one of the closest $k$ nodes to $v$ (with ties broken arbitrarily).
\end{restatable}



\apspQuery*
\begin{proofof}{\cref{claim:hc:apspQuery}}
    To approximate the distance $d_G(s, t)$, we compute $\min\set{d_G^{n^{1/2}}(s, t), d_G(s, p(s)) + d_G(p(s), t)}$, where $p(s)$ is the closest node to $s$ in some globally known hitting set $A$ of all $N^{n^{1/2}}_G(s)$. Thus, while pre-possessing, we verify that each node $s$ knows $d_G(s, v)$ for each $v\in A$.

    \textbf{Pre-processing:}
    %
    First, we execute the algorithm from \cref{claim:hc:knearest} with $k=n^{1/2}$ to get the distance to each node in $N^{n^{1/2}}_G(v)$. Now, each node enters $A$ independently with probability $\tildeBigO{n^{-1/2}}$. W.h.p., the set $A$ is of size $\tildeBigO{n^{1/2}}$ and is a hitting set for each $N^{n^{1/2}}_G(v)$. Let $\varepsilon'=\varepsilon/3$. We compute $(1+\varepsilon')$-approximate MSSP from $A$ using
    $\tildeBigO{n^{1/2}}$ invocations of the $(1+\varepsilon)$ approximate SSSP algorithm \cite[Corollary 5]{Ghaffari2018NewDA}. Each $v$ computes $p(v)\in A\cap N_{G}^{n^{1/2}}(v)$, which is the sampled node closest to $v$, which exists in the set of its $n^{1/2}$ nearest neighbors \whp.
    
   Computing  $n^{1/2}$-nearest takes ${(k \cdot n^{4/3}/m + n^{5/3}/m + 1)}\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds, \whp The complexity of solving $n^{1/2}$-SSP is $n^{1/2}\cdot\tau_{\text{mix}} \cdot 2^{\bigO{\sqrt{log{n}}}}$ rounds \whp. Overall complexity of the pre-processing thus $(n^{1/2} + {n^{11/6}}/{m})\cdot\ensuremath{\tmix\cdot \twosqlgnlglgn}$ rounds \whp. 

    \textbf{Query:}
    %
    Whenever node $s_i$ needs to approximate its distance to $t_i$, the node $s_i$ requests from $t_i$ the distance to $p(s_i)$, for which $t_i$ knows a $(1+\varepsilon')$ approximation, $\tilde{d}(p(s_i), t_i)$, due to \cite[Corollary 5]{Ghaffari2018NewDA}.
    The node $s$ approximates its distance to $t_i$ as $\tilde{d}(s_i, t_i)=d(s_i, p(s_i)) + \tilde{d}(p(s_i), t_i)$. The approximation factor follows from \fullref{claim:3approximation}.
    To execute the routing, the nodes invoke \cref{claim:hc:routing}. The number of rounds for solving a query with load $\ell$ is  $\ell\cdot \ensuremath{\tmix\cdot \twosqlgnlglgn} $ \whp
\end{proofof}

By denoting $\delta$ as the minimal degree in the graph, one gets load $\ell \leq n/\delta$ and $m \geq n \cdot \delta$, which implies our main result \cref{cor:sublinearAPSP}.

{\renewcommand\footnote[1]{}\sublinearAPSP*}


Finally, we use our \wacc simulation together with \fullref{theorem:wacc:approxAPSP} to obtain our Scattered APSP algorithm in the \ensuremath{\mathsf{CONGEST}}\xspace model.

{\renewcommand\footnote[1]{}\SAPSPInHC*}
\begin{proofof}{\cref{theorem:hc:sapsp}}
    Simulate \fullref{theorem:wacc:approxAPSP} using \fullref{lemma:hc:waccSimulation}. Split the output of each node $u$ to two parts. The first part, $s_u$, is $\tilde O(n^{1/2})$ bits encoding the communication tokens of nodes which store the distances from $u$. Thus, the output capacity is $o_c=\tildeBigO{n^{1/2}}$. The communication tokens decoded from $s_u$, allow $u$ to know where its distances are stored. The second part of the output of $u$ is the auxiliary output which is the distances it knows. Thus, the algorithm completes in 
    $((n^{11/6}/m + n^{1/3} + m / n)/\varepsilon + n^{1/2})\ensuremath{\tmix\cdot \twosqlgnlglgn}$
    rounds, \whp 
\end{proofof}





\section{Discussion}
\label{sec:discussion}
We believe that additional problems in various fundamental distributed settings could be solvable using our infrastructure for sparsity aware computation. This is a broad open direction for further research.


With respect to the specific results shown here, a major goal would be to construct a  more sparse hopset in the \wacc model. 
Further, one could attempt to show sparse matrix multiplication algorithms which relax the assumption that the input matrices and output matrix are bounded by the same number of finite elements, as this could directly improve the complexity of our 
$k$-SSP algorithm.
Either of these improvements is likely to significantly reduce the round complexity of many of our end results, in both the \ensuremath{\mathsf{Hybrid}}\xspace and \ensuremath{\mathsf{CONGEST}}\xspace models.




\section*{Acknowledgements}
This project was partially supported by the European Union’s Horizon 2020 Research and Innovation Programme under grant agreement no. 755839. The authors would like to thank Michal Dory and Yuval Efron for various helpful conversations. We also thank Fabian Kuhn for sharing a preprint of \cite{kuhn2020computing} with us.


\bibliographystyle{plainurl}
