Back to Search
Start Over
Communicating Reliably in Multihop Dynamic Networks despite Byzantine Failures
- Source :
- Proceedings of the International Symposium on Reliable Distributed Systems (SRDS2015), The International Symposium on Reliable Distributed Systems (SRDS2015), The International Symposium on Reliable Distributed Systems (SRDS2015), Sep 2015, Montreal, Canada, SRDS
- Publication Year :
- 2015
- Publisher :
- HAL CCSD, 2015.
-
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.
- Subjects :
- 020203 distributed computing
Computer science
business.industry
Distributed computing
Reliability (computer networking)
Cryptography
Context (language use)
0102 computer and information sciences
02 engineering and technology
[INFO] Computer Science [cs]
Network topology
Grid
01 natural sciences
Constructive
Quantum Byzantine agreement
010201 computation theory & mathematics
0202 electrical engineering, electronic engineering, information engineering
[INFO]Computer Science [cs]
business
Byzantine fault tolerance
ComputingMilieux_MISCELLANEOUS
Computer network
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Proceedings of the International Symposium on Reliable Distributed Systems (SRDS2015), The International Symposium on Reliable Distributed Systems (SRDS2015), The International Symposium on Reliable Distributed Systems (SRDS2015), Sep 2015, Montreal, Canada, SRDS
- Accession number :
- edsair.doi.dedup.....87f45720a819642bca8c76d787095d25