Skip to Main content Skip to Navigation
Reports

Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults

Abstract : We consider the problem of transmitting information reliably from a source node to a sink node in a dynamic multihop network, in spite of the presence of Byzantine nodes. Byzantine nodes behave arbitrarily, and can tamper with messages or forward spurious ones. Previous work has shown that reliable communication in the presence of k Byzantine failures is possible if and only if there are 2k+1 node-disjoint paths from the source to the sink. However, this result relies on Menger's theorem (the equivalence between node cut and connectivity), which only holds in static networks. In this paper, we prove the necessary and sufficient condition for reliable communication in dynamic networks, where the topology can vary with time. We then check if this condition is satisfied in several cases of study (robots moving on a grid, participants interacting in a conference, mobile agents in the subway...) and show the interest of this multihop approach for reliable communication in dynamic networks.
Complete list of metadatas

https://hal.sorbonne-universite.fr/hal-00940569
Contributor : Alexandre Maurer <>
Submitted on : Saturday, February 1, 2014 - 7:39:04 PM
Last modification on : Friday, January 8, 2021 - 5:38:04 PM
Long-term archiving on: : Sunday, April 9, 2017 - 5:33:01 AM

Files

bare_conf-copy.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00940569, version 1
  • ARXIV : 1402.0121

Citation

Alexandre Maurer, Sébastien Tixeuil, Xavier Défago. Reliable Communication in a Dynamic Network in the Presence of Byzantine Faults. 2014. ⟨hal-00940569v1⟩

Share

Metrics

Record views

298

Files downloads

252