Optimal-time adaptive strong renaming, with applications to counting
DOI10.1145/1993806.1993850zbMATH Open1321.68454OpenAlexW1966074520MaRDI QIDQ2943401FDOQ2943401
Authors: Dan Alistarh, James Aspnes, Keren Censor-Hillel, Morteza Zadimoghaddam, Seth Gilbert 
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://infoscience.epfl.ch/record/164269/files/camera-ready.pdf
Recommendations
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
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 (10)
- Randomized loose renaming in \(O(\log \log n)\) time
- Adaptive and efficient algorithms for lattice agreement and renaming
- Fast randomized test-and-set and renaming
- Efficient randomized test-and-set implementations
- Upper bound on the complexity of solving hard renaming
- An almost tight RMR lower bound for abortable test-and-set
- Lower bounds for restricted-use objects
- Tight bounds for asynchronous renaming
- Randomized consensus with regular registers
- Fully-adaptive algorithms for long-lived renaming
This page was built for publication: Optimal-time adaptive strong renaming, with applications to counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943401)
