A deterministic algorithm for the MST problem in constant rounds of congested clique
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
A deterministic algorithm for the MST problem in constant rounds of congested clique. / Nowicki, Krzysztof.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, Inc., 2021. p. 1154-1165.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - A deterministic algorithm for the MST problem in constant rounds of congested clique
AU - Nowicki, Krzysztof
N1 - Publisher Copyright: © 2021 ACM.
PY - 2021
Y1 - 2021
N2 - In this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model. In the Congested 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 O(logn) bit messages. The studies of this model began with the MST problem: in the paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05] that defines the Congested Clique model the authors give a deterministic O(loglogn) round algorithm that improved over a trivial O(logn) round adaptation of Borůvka's algorithm. There was a sequence of gradual improvements to this result: an O(logloglogn) round algorithm by Hegeman, Pandurangan, Pemmaraju, Sardeshmukh, and Scquizzato [PODC'15], an O(log? n) round algorithm by Ghaffari and Parter, [PODC'16] and an O(1) round algorithm by Jurdzi?ski and Nowicki, [SODA'18], but all those algorithms were randomized. Therefore, the question about the existence of any deterministic o(loglogn) round algorithms for the Minimum Spanning Tree problem remains open since the seminal paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05]. Our result resolves this question and establishes that O(1) rounds is enough to solve the MST problem in the Congested 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 a variant of the MPC model using machines with local memory of size O(n).
AB - In this paper we show that the Minimum Spanning Tree problem (MST) can be solved deterministically in O(1) rounds of the Congested Clique model. In the Congested 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 O(logn) bit messages. The studies of this model began with the MST problem: in the paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05] that defines the Congested Clique model the authors give a deterministic O(loglogn) round algorithm that improved over a trivial O(logn) round adaptation of Borůvka's algorithm. There was a sequence of gradual improvements to this result: an O(logloglogn) round algorithm by Hegeman, Pandurangan, Pemmaraju, Sardeshmukh, and Scquizzato [PODC'15], an O(log? n) round algorithm by Ghaffari and Parter, [PODC'16] and an O(1) round algorithm by Jurdzi?ski and Nowicki, [SODA'18], but all those algorithms were randomized. Therefore, the question about the existence of any deterministic o(loglogn) round algorithms for the Minimum Spanning Tree problem remains open since the seminal paper by Lotker, Pavlov, Patt-Shamir, and Peleg [SPAA'03, SICOMP'05]. Our result resolves this question and establishes that O(1) rounds is enough to solve the MST problem in the Congested 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 a variant of the MPC model using machines with local memory of size O(n).
KW - Congested Clique
KW - Deterministic Algorithms
KW - Distributed Algorithms
KW - Graph algorithms
KW - MapReduce
KW - Massively Parallel Algorithms
KW - Minimum Spanning Tree
KW - MST
KW - Parallel Algorithms
U2 - 10.1145/3406325.3451136
DO - 10.1145/3406325.3451136
M3 - Article in proceedings
AN - SCOPUS:85106205723
SP - 1154
EP - 1165
BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Khuller, Samir
A2 - Williams, Virginia Vassilevska
PB - Association for Computing Machinery, Inc.
T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Y2 - 21 June 2021 through 25 June 2021
ER -
ID: 306691028