Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time

DOI10.1145/2785953zbMATH Open1426.68025OpenAlexW2102764738MaRDI QIDQ3177735FDOQ3177735

Michel Raynal, Achour Mostefaoui, Hamouma Moumen

Publication date: 2 August 2018

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

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

zbMATH Keywords

randomized algorithmconsensussimplicitydistributed algorithmasynchronous message-passing systemByzantine processbroadcast abstractionsignature-free algorithmcommon coinoptimal resilience

Mathematics Subject Classification ID

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

Cited In (11)

• Improved extension protocols for Byzantine broadcast and agreement
• Byzantine consensus is \(\Theta(n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony!
• Asymmetric distributed trust
• Randomized \(k\)-set agreement in crash-prone and Byzantine asynchronous systems
• Process-commutative distributed objects: from cryptocurrencies to Byzantine-fault-tolerant CRDTs
• About informatics, distributed computing, and our job: a personal view
• Consensus in Byzantine asynchronous systems
• Towards achieving asynchronous MPC with linear communication and optimal resilience
• Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^2)\) messages, and constant time
• Not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP
• Synchronous consensus with optimal asynchronous fallback guarantees

This page was built for publication: Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time

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