The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model

DOI10.1007/978-3-319-42634-1_15zbMath1476.68099OpenAlexW2379659230MaRDI QIDQ2817860

Ivan Rapaport, Florent Becker, Antonio Fernández Anta, Eric Rémila

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_15

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Network protocols (68M12)

Related Items

Proof-labeling schemes: broadcast, unicast and in between

Cites Work

• Unnamed Item
• An information statistics approach to data stream and communication complexity
• Lower bounds on the multiparty communication complexity
• Algebraic methods in the congested clique
• Allowing each node to communicate only once in a distributed system: shared whiteboard models
• Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
• Toward Optimal Bounds in the Congested Clique
• Brief Announcement
• On Information Complexity in the Broadcast Model
• The round complexity of distributed sorting
• On the power of the congested clique model
• Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model
• The Probabilistic Communication Complexity of Set Intersection
• Distributed Computing: A Locality-Sensitive Approach
• Communication Complexity
• “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
• Optimal deterministic routing and sorting on the congested clique
• Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
• The Simultaneous Number-in-Hand Communication Model for Networks: Private Coins, Public Coins and Determinism
• Lessons from the Congested Clique Applied to MapReduce