The round complexity of distributed sorting, extended abstract

DOI10.1145/1993806.1993851MaRDI QIDQ2943403zbMATH OpenOpenAlexFDO

Authors 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

communication complexitynetwork algorithmsdistributed sortingcongest model

Mathematics Subject Classification ID

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

Recommendations

• The bit complexity of distributed sorting
• The complexity of sorting on distributed systems
• Optimal Distributed Algorithms for Sorting and Ranking
• Optimal deterministic routing and sorting on the congested clique
• Sorting and Selecting in Rounds

Cites work

• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(11)

• Fault-tolerant graph realizations in the congested clique
• Derandomizing local distributed algorithms under bandwidth restrictions
• Tight bounds for parallel randomized load balancing
• Optimal deterministic routing and sorting on the congested clique
• Large-scale distributed algorithms for facility location with outliers
• The effect of range and bandwidth on the round complexity in the congested clique model
• Sub-logarithmic distributed algorithms for metric facility location
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Lessons from the congested clique applied to MapReduce
• Sorting and Selecting in Rounds
• scientific article; zbMATH DE number 4043263 (Why is no real title available?)

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

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