Communication-efficient randomized consensus

DOI10.1007/S00446-017-0315-1MaRDI QIDQ2075627zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dan Alistarh, James Aspnes, Valerie King, Jared Saia

Publication date 15 February 2022

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00446-017-0315-1

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14)

Recommendations

• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Simple constant-time consensus protocols in realistic failure models
• On the complexity of asynchronous gossip
• Randomized consensus in expected O(n n) individual work
• scientific article; zbMATH DE number 6297761

Cites work

• Approximate shared-memory counting despite a strong adversary
• Fast randomized consensus using shared memory
• Fast scalable deterministic consensus for crash failures
• scientific article; zbMATH DE number 432838 (Why is no real title available?)
• scientific article; zbMATH DE number 3723610 (Why is no real title available?)
• Impossibility of distributed consensus with one faulty process
• Lower bounds for distributed coin-flipping and randomized consensus
• On the space complexity of randomized synchronization
• Polylog randomized wait-free consensus
• Polylogarithmic concurrent data structures from monotone circuits
• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Randomized consensus in expected O(n n) individual work
• Randomized protocols for asynchronous consensus
• Reaching Agreement in the Presence of Faults
• Robust gossiping with an application to consensus
• Sharing memory robustly in message-passing systems
• The Byzantine Generals Problem
• The correctness proof of Ben-Or's randomized consensus algorithm
• Tight bounds for asynchronous randomized consensus
• Time and Communication Efficient Consensus for Crash Failures
• Unreliable failure detectors for reliable distributed systems

Cited in

(21)

• Compressing communication in distributed protocols
• The correctness proof of Ben-Or's randomized consensus algorithm
• Communication-efficient and crash-quiescent omega with unknown membership
• A crash-tolerant consensus algorithm in presence of probabilistic message omission
• Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers
• Lower bounds for distributed coin-flipping and randomized consensus
• Fast randomized consensus using shared memory
• On the Message Complexity of Indulgent Consensus
• Randomized parallel communications on an extension of the omega network
• Simple constant-time consensus protocols in realistic failure models
• Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds
• scientific article; zbMATH DE number 1256649 (Why is no real title available?)
• scientific article; zbMATH DE number 1559571 (Why is no real title available?)
• Resilient Randomized Quantized Consensus
• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Sublinear message bounds for randomized agreement
• scientific article; zbMATH DE number 6297761 (Why is no real title available?)
• Faster randomized consensus with an oblivious adversary
• Brief Announcement: Improved Consensus in Quantum Networks
• Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
• Distributed fast crash-tolerant consensus with nearly-linear quantum communication

This page was built for publication: Communication-efficient randomized consensus

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