Asynchronous byzantine agreement protocols
From MaRDI portal
A consensus protocol enables a system of n asynchronous processes, some of them faulty, to reach agreement. Both the processes and the message system are capable of cooperating to prevent the correct processes from reaching decision. A protocol is t-resilient if in the presence of up to t faulty processes it reaches agreement with probability 1. Byzantine processes are faulty processes can be deviate arbitrarily from the protocol; Fail-Stop processes can just stop participating in it. In a recent paper, t-resilient randomized consensus protocols were presented for \(t<n/5\). We improve this to \(t<n/3\), thus matching the known lower bound on the number of correct processes necessary for consensus. The protocol uses a general technique in which the behavior of the Byzantine processes is restricted by the use of a broadcast protocol that filters some of the messages. The apparent behavior of the byzantine processes, filtered by the broadcast protocol, is similar to that of fail-stop processes. Plugging the broadcast protocol as a communicating primitive into an agreement protocol for fail-stop processes gives the result. This technique, of using broadcast protocols to reduce the power of the faulty processes and then using them as communication primitives in algorithms designed for weaker failure models, was used successfully in other contexts.
Recommendations
- Asynchronous consensus and broadcast protocols
- On Optimal Probabilistic Asynchronous Byzantine Agreement
- Randomized protocols for asynchronous consensus
- An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
- When 3f + 1 Is Not Enough: Tradeoffs for Decentralized Asynchronous Byzantine Consensus
Cites work
Cited in
(92)- Randomized k-set agreement in crash-prone and Byzantine asynchronous systems
- Consensus in Byzantine asynchronous systems
- Byzantine-resistant total ordering algorithms.
- Low complexity Byzantine-resilient consensus
- Lower bounds for asynchronous consensus
- Byzantine-tolerant causal broadcast
- Consensus using omega in asynchronous systems with unknown membership and degenerative Byzantine failures
- Always have a backup plan: fully secure synchronous MPC with asynchronous fallback
- Making Byzantine consensus live
- High-threshold AVSS with optimal communication complexity
- Revisiting asynchronous fault tolerant computation with optimal resilience
- Synchronous consensus with optimal asynchronous fallback guarantees
- Byzantine preferential voting
- A reduction theorem for randomized distributed algorithms under weak adversaries
- Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^2)\) messages, and constant time
- Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography
- On the (limited) power of non-equivocation
- An almost-surely terminating polynomial protocol for asynchronous Byzantine agreement with optimal resilience
- The contest between simplicity and efficiency in asynchronous Byzantine agreement
- Byzantine Agreement Using Partial Authentication
- Signature-free asynchronous binary Byzantine consensus with \(t<n/3\), \(O(n^2)\) messages, and \(O(1)\) expected time
- Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^{2})\) messages, and constant time
- When 3f + 1 Is Not Enough: Tradeoffs for Decentralized Asynchronous Byzantine Consensus
- Reaching approximate agreement in the presence of faults
- Asynchronous consensus and broadcast protocols
- An O (log n ) expected rounds randomized byzantine generals protocol
- A compiler that increases the fault tolerance of asynchronous protocols
- Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds
- Using asynchrony and zero degradation to speed up indulgent consensus protocols
- An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
- scientific article; zbMATH DE number 4121395 (Why is no real title available?)
- On the versatility of Bracha's Byzantine reliable broadcast algorithm
- Federated Byzantine quorum systems
- A hybrid protocol to solve authenticated Byzantine consensus
- Randomized protocols for asynchronous consensus
- Resilient-optimal interactive consistency in constant time
- Analysis of the Blockchain Protocol in Asynchronous Networks
- On Optimal Probabilistic Asynchronous Byzantine Agreement
- On Byzantine Agreement over (2,3)-Uniform Hypergraphs
- Principles of Distributed Systems
- Verification of randomized consensus algorithms under round-rigid adversaries
- Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker
- Asynchronous Byzantine reliable broadcast with a message adversary
- Total ordering algorithms for asynchronous Byzantine systems
- Cross-chain payment protocols with success guarantees
- Expected linear round synchronization: the missing link for linear Byzantine SMR
- Consensus on demand
- Clairvoyant state machine replications
- Distributed CONGEST Algorithms against Mobile Adversaries
- Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
- Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn
- Making Byzantine consensus live
- Not a COINcidence: sub-quadratic asynchronous Byzantine agreement WHP
- Expected linear round synchronization: the missing link for linear Byzantine SMR
- Improved extension protocols for Byzantine broadcast and agreement
- From partial to global asynchronous reliable broadcast
- Byzantine lattice agreement in synchronous message passing systems
- Brief announcement: Multi-threshold asynchronous reliable broadcast and consensus
- Lightweight asynchronous verifiable secret sharing with optimal resilience
- Byzantine consensus is \(\Theta(n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony!
- Good-case early-stopping latency of synchronous Byzantine reliable broadcast: the deterministic case
- Liveness and latency of Byzantine state-machine replication
- Concurrent asynchronous Byzantine agreement in expected-constant rounds, revisited
- Asymmetric distributed trust
- Communication games, sequential equilibrium, and mediators
- Process-commutative distributed objects: from cryptocurrencies to Byzantine-fault-tolerant CRDTs
- Perfect asynchronous MPC with linear communication overhead
- Fast batched asynchronous distributed key generation
- Closing the efficiency gap between synchronous and network-agnostic consensus
- Detecting causality in the presence of Byzantine processes: the case of synchronous systems
- Dynamic Byzantine reliable broadcast
- Information theoretic HotStuff
- Multi-threshold asynchronous reliable broadcast and consensus
- Byzantine lattice agreement in asynchronous systems
- Semiframes: the algebra of semitopologies and actionable coalitions
- Byzantine reliable broadcast and tendermint consensus with trusted components
- Asymptotically optimal adaptive asynchronous common coin and DKG with silent setup
- MiniCast: minimizing the communication complexity of reliable broadcast
- Expected constant round Byzantine broadcast under dishonest majority
- Semitopology: a topological approach to decentralized collaborative action
- Asynchronous agreement on a core set in constant expected time and more efficient asynchronous VSS and MPC
- DRAGON: decentralization at the cost of representation after arbitrary GrOupiNg and its applications to sub-cubic DKG and interactive consistency
- Bounding the communication complexity of fault-tolerant common coin tossing
- Byzantine agreement with optimal resilience via statistical fraud detection
- Is it even possible? On the parallel composition of asynchronous MPC protocols
- Byzantine-tolerant distributed grow-only sets: specification and applications
- Centroid approximation with multidimensional approximate agreement protocols
- Fast and efficient perfectly secure network-agnostic secure computation
- Byzantine-tolerant privacy-preserving atomic register
- On the nonexistence of resilient consensus protocols
- Multidimensional agreement in Byzantine systems
- Knowledge and common knowledge in a Byzantine environment: Crash failures
This page was built for publication: Asynchronous byzantine agreement protocols
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091131)
