Randomized consensus with regular registers

DOI10.1016/j.ipl.2021.106173OpenAlexW3192049267MaRDI QIDQ2059870

Sam Toueg, Vassos Hadzilacos, Xing Hu

Publication date: 14 December 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.06771

zbMATH Keywords

distributed computingshared memoryconsensusrandomized distributed algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

On atomic registers and randomized consensus in m\&m systems

Cites Work

• From binary consensus to multivalued consensus in asynchronous message-passing systems
• On interprocess communication. II: Algorithms
• Wait-freedom is harder than lock-freedom under strong linearizability
• Strongly linearizable implementations
• Polylog randomized wait-free consensus
• Optimal-time adaptive strong renaming, with applications to counting
• Lower bounds for distributed coin-flipping and randomized consensus
• Tight Bounds for Asynchronous Renaming
• Tight bounds for asynchronous randomized consensus
• Fast randomized consensus using shared memory
• Fast Randomized Test-and-Set and Renaming
• Time- and Space-Efficient Randomized Consensus
• Randomized protocols for asynchronous consensus
• Linearizable implementations do not suffice for randomized distributed computation