Trading off t-resilience for efficiency in asynchronous Byzantine reliable broadcast

DOI10.1142/S0129626416500171zbMATH Open1376.68027arXiv1510.06882OpenAlexW2566112925MaRDI QIDQ4598930FDOQ4598930

Authors: Damien Imbs, Michel Raynal 

Publication date: 15 December 2017

Published in: Parallel Processing Letters (Search for Journal in Brave)

Abstract: This paper presents a simple and efficient reliable broadcast algorithm for asynchronous message-passing systems made up of $n$ processes, among which up to $t<n/5$ may behave arbitrarily (Byzantine processes). This algorithm requires two communication steps and $n^2-1$ messages. When compared to Bracha's algorithm, which is resilience optimal ($t<n/3$) and requires three communication steps and $2n^2-n-1$ messages, the proposed algorithm shows an interesting tradeoff between communication efficiency and $t$-resilience.

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

Recommendations

• On the versatility of Bracha's Byzantine reliable broadcast algorithm
• Signature-free asynchronous binary Byzantine consensus with \(t<n/3\), \(O(n^2)\) messages, and \(O(1)\) expected time
• Signature-free asynchronous byzantine consensus with t < n/3 and o(n ² ) messages
• Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn
• Asynchronous Byzantine agreement with optimal resilience

zbMATH Keywords

distributed computingfault-toleranceasynchronous systemreliable broadcastmessage-passingByzantine process

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14) Network protocols (68M12)

Cited In (7)

• Good-case early-stopping latency of synchronous Byzantine reliable broadcast: the deterministic case
• Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn
• On the versatility of Bracha's Byzantine reliable broadcast algorithm
• Detecting causality in the presence of Byzantine processes: the case of synchronous systems
• Asynchronous Byzantine reliable broadcast with a message adversary
• Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer
• Byzantine-tolerant causal broadcast

This page was built for publication: Trading off \(t\)-resilience for efficiency in asynchronous Byzantine reliable broadcast

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