Lower Bounds for Randomized Consensus under a Weak Adversary

DOI10.1137/090751906zbMath1214.68241OpenAlexW2029701567MaRDI QIDQ5390620

Keren Censor-Hillel, Hagit Attiya

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/64943

zbMATH Keywords

lower bounddistributed computingrandomized algorithmsmessage passingshared memoryconsensus

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Randomized algorithms (68W20) Distributed algorithms (68W15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

On the round complexity of randomized Byzantine agreement ⋮ Round-optimal Byzantine agreement ⋮ A modular approach to shared-memory consensus, with applications to the probabilistic-write model ⋮ The correctness proof of Ben-Or's randomized consensus algorithm ⋮ On the complexity of asynchronous agreement against powerful adversaries ⋮ Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ⋮ Tight bounds for adopt-commit objects ⋮ Efficient randomized test-and-set implementations ⋮ Faster randomized consensus with an oblivious adversary ⋮ Sub-logarithmic Test-and-Set against a Weak Adversary

This page was built for publication: Lower Bounds for Randomized Consensus under a Weak Adversary