Skip to Main content Skip to Navigation

Parameterizable Byzantine Broadcast in Loosely Connected Networks

Abstract : We consider the problem of reliably broadcasting information in a multihop asynchronous network, despite the presence of Byzantine failures: some nodes are malicious and behave arbitrarly. We focus on non-cryptographic solutions. Most existing approaches give conditions for perfect reliable broadcast (all correct nodes deliver the good information), but require a highly connected network. A probabilistic approach was recently proposed for loosely connected networks: the Byzantine failures are randomly distributed, and the correct nodes deliver the good information with high probability. A first solution require the nodes to initially know their position on the network, which may be difficult or impossible in self-organizing or dynamic networks. A second solution relaxed this hypothesis but has much weaker Byzantine tolerance guarantees. In this paper, we propose a parameterizable broadcast protocol that does not require nodes to have any knowledge about the network. We give a deterministic technique to compute a set of nodes that always deliver authentic information, for a given set of Byzantine failures. Then, we use this technique to experimentally evaluate our protocol, and show that it significantely outperforms previous solutions with the same hypotheses. Important disclaimer: these results have NOT yet been published in an international conference or journal. This is just a technical report presenting intermediary and incomplete results. A generalized version of these results may be under submission.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download
Contributor : Alexandre Maurer <>
Submitted on : Sunday, December 8, 2013 - 3:51:11 AM
Last modification on : Friday, January 8, 2021 - 5:32:04 PM
Long-term archiving on: : Saturday, April 8, 2017 - 5:27:46 AM


Files produced by the author(s)


  • HAL Id : hal-00777155, version 2
  • ARXIV : 1301.3996


Alexandre Maurer, Sébastien Tixeuil. Parameterizable Byzantine Broadcast in Loosely Connected Networks. 2012. ⟨hal-00777155v2⟩



Record views


Files downloads