Random Sampling Applied to the MST Problem in the Node Congested Clique Model

The Congested Clique model proposed by Lotker et al.[SICOMP’05] was introduced in order to provide a simple abstraction for overlay networks. Congested Clique is a model of distributed (or parallel) computing, in which there are $n$ players with unique identifiers from set [n], which perform computations in synchronous rounds. Each round consists of the phase of unlimited local computation and the communication phase. While communicating, each pair of players is allowed to exchange a single message of size $O(\log n)$ bits. Since, in a single round, each player can communicate with even $\mathrm{\Theta }(n)$ other players, the model seems to be to powerful to imitate bandwidth restriction emerging from the underlying network. In this paper we study a restricted version of the Congested Clique model, the Node Congested Clique (NCC) model, proposed by Augustine et al.[arxiv1805], in which a player is allowed to send/receive only $O(\log n)$ messages per communication phase. More precisely, we provide communication primitives that improve the round complexity of the MST algorithm by Augustine et al. [arxiv1805] to $O(\log^3 n)$rounds,andgivean$O(\log^2 n)$ round algorithm solving the Spanning Forest (SF) problem. Furthermore, we present an approach based on the random sampling technique by Karger et al.[JACM’95] that gives an $O(\log^2 n \log \Delta / \log \log n)$ round algorithm for the Minimum Spanning Forest (MSF) problem. Besides the faster SF/ MSF algorithms we consider the key contributions to be

• an efficient implementation of basic protocols in the NCC model
• a tighter analysis of a special case of the sampling approach by Karger et al.[JACM’95] and related results by Pemmaraju and Sardeshmukh [FSTTCS’16]
• efficient k-sparse recovery data structure that requires $O((k +\log n)\log n\log k)$bitsandprovidesrecoveryprocedurethatrequires$O((k +\log n)\log k)$ steps