The role of randomness in the broadcast congested clique model

DOI10.1016/j.ic.2020.104669OpenAlexW3106831823MaRDI QIDQ2051760

Ivan Rapaport, Ioan Todinca, Pedro Montealegre, Florent Becker

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2020.104669

zbMATH Keywords

distributed computingbroadcast congested cliquemessage size complexityprivate and public coinssimultaneous multi-party communication

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• MapReduce
• Hadoop
• Dryad
• Pregel
• Spark

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On randomized one-round communication complexity
• Errata for: ``On randomized one-round communication complexity
• Two rounds are enough for reconstructing any graph (class) in the congested clique model
• Algebraic methods in the congested clique
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity
• The communication complexity of distributed task allocation
• On the power of the congested clique model
• Powers of tensors and fast matrix multiplication
• Communication Complexity
• Connectivity Lower Bounds in Broadcast Congested Clique
• Brief Announcement
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history

This page was built for publication: The role of randomness in the broadcast congested clique model