61
views
0
recommends
+1 Recommend
0 collections
    2
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We consider the following problem: two nodes want to reliably communicate in a dynamic multihop network where some nodes have been compromised, and may have a totally arbitrary and unpredictable behavior. These nodes are called Byzantine. We consider the two cases where cryptography is available and not available. We prove the necessary and sufficient condition (that is, the weakest possible condition) to ensure reliable communication in this context. Our proof is constructive, as we provide Byzantine-resilient algorithms for reliable communication that are optimal with respect to our impossibility results. In a second part, we investigate the impact of our conditions in three case studies: participants interacting in a conference, robots moving on a grid and agents in the subway. Our simulations indicate a clear benefit of using our algorithms for reliable communication in those contexts.

          Related collections

          Author and article information

          Journal
          2014-02-01
          2015-02-16
          Article
          1402.0121
          10f9fc0e-b851-4a20-a106-b7ca282a30bd

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          cs.DC cs.DS cs.NI
          ccsd

          Data structures & Algorithms,Networking & Internet architecture
          Data structures & Algorithms, Networking & Internet architecture

          Comments

          Comment on this article