The role of randomness in the broadcast congested clique model

DOI10.1016/J.IC.2020.104669MaRDI QIDQ2051760zbMATH OpenOpenAlexFDO

Authors Florent Becker, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

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

broadcast congested cliquedistributed computingmessage size complexityprivate and public coinssimultaneous multi-party communication

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Broadcast Congested Clique
• On Randomized Broadcasting in Power Law Networks
• The impact of locality in the broadcast congested clique model
• Randomized broadcast in networks
• Brief announcement: A hierarchy of congested clique models, from broadcast to unicast
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
• Broadcasting in random graphs

Cites work

• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• Brief announcement: Deterministic graph connectivity in the broadcast congested clique
• Communication Complexity
• Connectivity Lower Bounds in Broadcast Congested Clique
• Errata for: ``On randomized one-round communication complexity
• scientific article; zbMATH DE number 1256775 (Why is no real title available?)
• scientific article; zbMATH DE number 1769898 (Why is no real title available?)
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On randomized one-round communication complexity
• On the power of the congested clique model
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
• Powers of tensors and fast matrix multiplication
• Public vs. private randomness in simultaneous multi-party communication complexity
• The communication complexity of distributed task allocation
• Two rounds are enough for reconstructing any graph (class) in the congested clique model

Cited in

(3)

• Brief announcement: A hierarchy of congested clique models, from broadcast to unicast
• The effect of range and bandwidth on the round complexity in the congested clique model
• Broadcast Congested Clique

Describes a project that uses

Uses Software

• MapReduce
• Hadoop
• Dryad
• Pregel
• Spark

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051760)