Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadatas

https://hal.sorbonne-universite.fr/hal-00777155
Contributor : Alexandre Maurer <>
Submitted on : Thursday, January 17, 2013 - 2:43:08 AM
Last modification on : Friday, January 8, 2021 - 5:32:04 PM
Long-term archiving on: : Saturday, April 1, 2017 - 6:27:10 AM

Files

bare_conf.pdf
Files produced by the author(s)

Identifiers

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

Citation

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

Share

Metrics

Record views

90

Files downloads

74