Abstract : We propose a framework to build formal developments for robot networks using the Coq proof assistant, to state and prove formally various properties. We focus in this paper on impossibility proofs, as it is natural to take advantage of the Coq higher order calculus to reason about algorithms as abstract objects. We present in particular formal proofs of two impossibility results for convergence of oblivious mobile robots if respectively more than one half and more than one third of the robots exhibit Byzantine failures, starting from the original theorems by Bouzid et al.. Thanks to our formalisation, the corresponding Coq developments are quite compact. To our knowledge, these are the first certified (in the sense of formally proved) impossibility results for robot networks.
Type de document :
Communication dans un congrès
International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2013, Osaka, Japan. Springer, 8255, pp.178-190, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-319-03089-0_13〉
https://hal.sorbonne-universite.fr/hal-00930267
Contributeur : Sébastien Tixeuil
<>
Soumis le : mardi 14 janvier 2014 - 15:30:47
Dernière modification le : mardi 10 juillet 2018 - 17:02:03
Cédric Auger, Zohir Bouzid, Pierre Courtieu, Sébastien Tixeuil, Xavier Urbain. Certified Impossibility Results for Byzantine-Tolerant Mobile Robots. International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2013, Osaka, Japan. Springer, 8255, pp.178-190, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-319-03089-0_13〉. 〈hal-00930267〉
