In this paper, we show that the Minimum Spanning Tree problem can be solved \emph{ deterministically}, in $\mathcal{ O}(1)$ rounds of the $\mathsf{ Congested}$ $\mathsf{ Clique}$ model. In the $\mathsf{ Congested}$ $\mathsf{ Clique}$ model, there are $n$ players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange $\mathcal{ O}(\log n)$ bit messages. The studies of this model began with the MST problem: in the paper by Lotker et al.[SPAA'03, SICOMP'05] that defines the $\mathsf{ Congested}$ $\mathsf{ Clique}$ model the authors give a deterministic $\mathcal{ O}(\log \log n)$ round algorithm that improved over a trivial $\mathcal{ O}(\log n)$ round adaptation of Bor\r{ u}vka's algorithm. There was a sequence of gradual improvements to this result: an $\mathcal{ O}(\log \log \log n)$ round algorithm by Hegeman et al. [PODC'15], an $\mathcal{ O}(\log^* n)$ round algorithm by Ghaffari and Parter, [PODC'16] and an $\mathcal{ O}(1)$ round algorithm by Jurdzi\'nski and Nowicki, [SODA'18], but all those algorithms were randomized, which left the question about the existence of any deterministic $o(\log \log n)$ round algorithms for the Minimum Spanning Tree problem open. Our result resolves this question and establishes that $\mathcal{ O}(1)$ rounds is enough to solve the MST problem in the $\mathsf{ Congested}$ $\mathsf{ Clique}$ model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to some variants of the $\mathsf{ MPC}$ model.
Categories: cs.DS cs.DC