The round complexity of distributed sorting

DOI10.1145/1993806.1993851zbMath1321.68236OpenAlexW2056695987MaRDI QIDQ2943403

Boaz Patt-Shamir, Marat Teplitsky

Publication date: 11 September 2015

Published in: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993806.1993851

zbMATH Keywords

network algorithmscommunication complexitydistributed sortingcongest model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (9)

Tight bounds for parallel randomized load balancing ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Lessons from the congested clique applied to MapReduce ⋮ Fault-tolerant graph realizations in the congested clique ⋮ Algebraic methods in the congested clique ⋮ Unnamed Item ⋮ Sub-logarithmic distributed algorithms for metric facility location ⋮ The Effect of Range and Bandwidth on the Round Complexity in the Congested Clique Model ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE

Cites Work

• Unnamed Item
• Gradient clock synchronization in dynamic networks
• Consensus algorithms with one-bit messages
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Broadcasting in dynamic radio networks
• Programming simultaneous actions using common knowledge
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• Knowledge and common knowledge in a distributed environment
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• Perfectly secure message transmission
• Parsimonious flooding in dynamic graphs
• Optimal gradient clock synchronization in dynamic networks
• Almost-Everywhere Secure Computation

This page was built for publication: The round complexity of distributed sorting