Lower bounds for distributed coin-flipping and randomized consensus

DOI10.1145/278298.278304zbMath1065.68571OpenAlexW2047964326MaRDI QIDQ3158511

James Aspnes

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/278298.278304

zbMATH Keywords

class of collective coin-flipping gamesrandomized distributed algorithms with halting failures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (9)

A lower bound for adaptively-secure collective coin flipping protocols ⋮ On the complexity of asynchronous agreement against powerful adversaries ⋮ Brief Announcement: Improved Consensus in Quantum Networks ⋮ Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler ⋮ On the importance of having an identity or, is consensus really universal? ⋮ Hundreds of impossibility results for distributed computing ⋮ Randomized protocols for asynchronous consensus ⋮ Randomized consensus with regular registers ⋮ Communication-efficient randomized consensus

This page was built for publication: Lower bounds for distributed coin-flipping and randomized consensus