The round complexity of distributed sorting, extended abstract
DOI10.1145/1993806.1993851zbMATH Open1321.68236OpenAlexW2056695987MaRDI QIDQ2943403FDOQ2943403
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Flooding time in edge-Markovian dynamic graphs
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Parsimonious flooding in dynamic graphs
- Distributed computation in dynamic networks
- Continuous consensus via common knowledge
- Reaching Agreement in the Presence of Faults
- Knowledge and common knowledge in a distributed environment
- Perfectly secure message transmission
- Programming simultaneous actions using common knowledge
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Consensus algorithms with one-bit messages
- Broadcasting in dynamic radio networks
- Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
- Fault Tolerance in Networks of Bounded Degree
- Optimal gradient clock synchronization in dynamic networks
- Almost-Everywhere Secure Computation
- Gradient clock synchronization in dynamic networks
Cited In (11)
- Derandomizing local distributed algorithms under bandwidth restrictions
- Optimal deterministic routing and sorting on the congested clique
- Tight bounds for parallel randomized load balancing
- Large-scale distributed algorithms for facility location with outliers
- 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
- Sub-logarithmic distributed algorithms for metric facility location
- Lessons from the congested clique applied to MapReduce
- Sorting and Selecting in Rounds
- Title not available (Why is that?)
- Fault-tolerant graph realizations in the congested clique
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)
