2017/03/08 by Tomasz Jurdziński, Krzysztof Nowicki, Jurdzinski, Tomasz +1 · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1703.02743
openalex publication_date 2017/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The congested clique is a synchronous, message-passing model of distributed computing in which each computational unit (node) in each round can send message of O(log n) bits to each other node of the network, where n is the number of nodes. This model has been considered under two extreme scanarios: unicast or broadcast. In the unicast model, a node can send (possibly) different message to each other node of the network. In contrast, in the broadcast model each node sends a single (the same) message to all other nodes. We study the congested clique model parametrized by the range r, the maximum number of different messages a node can send in one round. Following recent progress in design of algorihms for graph connectivity and minimum span- ning forest (MSF) in the unicast congested clique, we study these problems in limited variants of the congested clique. We present the first sub-logarithmic algorithm for connected components in the broadcast congested clique. Then, we show that efficient unicast deterministic algorithm for MSF and randomized algorithm for connected components can be efficiently imple- mented in the rcast model with range r = 2, the weakest model of the congested clique above the broadcast variant (r = 1) in the hierarchy with respect to range. More importantly, our al- gorithms give the first solutions with optimal capacity of communication edges, while preserving small round complexity.