Lower bounds for randomized consensus under a weak adversary

DOI10.1145/1400751.1400793MaRDI QIDQ2934356zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Keren Censor-Hillel

Publication date 12 December 2014

Published in Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

consensusdistributed computinglower boundmessage passingrandomized algorithmsshared memory

Mathematics Subject Classification ID

Distributed systems (68M14) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Computation considerations and fast algorithms for calculating the diffraction integral
• scientific article; zbMATH DE number 6536453
• On the integration of highly oscillatory functions: Algorithms based on critical points and semi-periodic zones in scalar diffraction
• Schlömilch series that arise in diffraction theory and their efficient computation
• On an algorithm for calculating diffraction integrals

Cited in

(12)

• A bivalency proof of the lower bound for uniform consensus
• A reduction theorem for randomized distributed algorithms under weak adversaries
• The contest between simplicity and efficiency in asynchronous Byzantine agreement
• Lower bounds for distributed coin-flipping and randomized consensus
• Tight bounds for asynchronous randomized consensus
• scientific article; zbMATH DE number 1950667 (Why is no real title available?)
• scientific article; zbMATH DE number 1559571 (Why is no real title available?)
• Lower bounds for randomized consensus under a weak adversary
• Fault-tolerant algorithms for tick-generation in asynchronous logic: robust pulse generation
• Faster randomized consensus with an oblivious adversary
• Some lower bounds in dynamic networks with oblivious adversaries
• Closing the efficiency gap between synchronous and network-agnostic consensus

This page was built for publication: Lower bounds for randomized consensus under a weak adversary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934356)