Asynchronous Byzantine reliable broadcast with a message adversary

DOI10.1016/J.TCS.2023.114110MaRDI QIDQ6050128zbMATH OpenOpenAlexFDO

Authors Timothé Albouy, Davide Frey, Michel Raynal, François Taïani

Publication date 12 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.09992

zbMATH Keywords

asynchronous systemByzantine processeschurnmessage adversarymessage lossesmessage signaturesmessage-passingreliable broadcasttransient disconnection

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: This paper considers the problem of reliable broadcast in asynchronous authenticated systems, in which n processes communicate using signed messages and up to t processes may behave arbitrarily (Byzantine processes). In addition, for each message m broadcast by a correct (i.e., non-Byzantine) process, a message adversary may prevent up to d correct processes from receiving m. (This message adversary captures network failures such as transient disconnections, silent churn, or message losses.) Considering such a "double" adversarial context and assuming n > 3t + 2d, a reliable broadcast algorithm is presented. Interestingly, when there is no message adversary (i.e., d = 0), the algorithm terminates in two communication steps (so, in this case, this algorithm is optimal in terms of both Byzantine tolerance and time efficiency). It is then shown that the condition n > 3t + 2d is necessary for implementing reliable broadcast in the presence of both Byzantine processes and a message adversary (whether the underlying system is enriched with signatures or not).

Cites work

• Agreement in synchronous networks with ubiquitous faults
• Asynchronous byzantine agreement protocols
• Asynchronous consensus and broadcast protocols
• Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn
• Distributed computation in dynamic networks
• Fault-tolerant message-passing distributed systems. An algorithmic approach
• Introduction to Reliable and Secure Distributed Programming
• Money transfer made simple: a specification, a generic algorithm, and its proof
• On the versatility of Bracha's Byzantine reliable broadcast algorithm
• Reaching Agreement in the Presence of Faults
• Scalable Byzantine reliable broadcast
• Synchronous consensus under hybrid process and link failures
• Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
• The Byzantine Generals Problem
• The Byzantine generals strike again
• The Heard-Of model: computing in distributed systems with benign faults
• Time is not a healer (preliminary version)
• Trading off t-resilience for efficiency in asynchronous Byzantine reliable broadcast

Cited in

(5)

• Byzantine-tolerant causal broadcast
• Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions
• scientific article; zbMATH DE number 7650856 (Why is no real title available?)
• Scalable Byzantine reliable broadcast
• Process-commutative distributed objects: from cryptocurrencies to Byzantine-fault-tolerant CRDTs

This page was built for publication: Asynchronous Byzantine reliable broadcast with a message adversary

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