Optimal-time adaptive strong renaming, with applications to counting

DOI10.1145/1993806.1993850MaRDI QIDQ2943401zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

distributed computinglower boundsadaptive algorithmsshared memorysorting networksrenaming

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• Tight bounds for asynchronous renaming
• scientific article; zbMATH DE number 2006648
• Randomized loose renaming in \(O(\log \log n)\) time
• Fast randomized test-and-set and renaming
• Adaptive and efficient algorithms for lattice agreement and renaming

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

(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)