Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks

We consider the problem of approximate consensus in mobile networks containing Byzantine nodes. We assume that each correct node can communicate only with its neighbors and has no knowledge of the global topology. As all nodes have moving ability, the topology is dynamic. The number of Byzantine nodes is bounded by f and known by all correct nodes. We first introduce an approximate Byzantine consensus protocol which is based on the linear iteration method. As nodes are allowed to collect information during several consecutive rounds, moving gives them the opportunity to gather more values. We propose a novel sufficient and necessary condition to guarantee the final convergence of the consensus protocol. The requirement expressed by our condition is not "universal": in each phase it affects only a single correct node. More precisely, at least one correct node among those that propose either the minimum or the maximum value which is present in the network, has to receive enough messages (quantity constraint) with either higher or lower values (quality constraint). Of course, nodes' motion should not prevent this requirement to be fulfilled. Our conclusion shows that the proposed condition can be satisfied if the total number of nodes is greater than 3f+1.Nous considérons le problème du consensus approximatif dans des réseaux mobiles contenant des nœuds byzantins. Nous supposons que chaque nœud correct ne peut communiquer qu'avec ses voisins et n'a pas connaissance de la topologie globale. Comme tous les nœuds ont la possibilité de se déplacer, la topologie est dynamique. Le nombre de nœuds byzantins est borné par f et est connu de tous les nœuds corrects. Nous présentons tout d'abord un protocole de consensus approximatif byzantine qui est fondé sur la méthode d'itération linéaire. Comme les nœuds sont autorisés à collecter des informations lors de plusieurs tours consécutifs, le fait de se déplacer leur donne l'occasion de recueillir plus de valeurs. Nous proposons une nouvelle condition nécessaire et suffisante pour garantir la convergence finale du protocole de consensus. La contrainte exprimée par notre condition n'est pas "universelle": lors de chaque phase, elle ne concerne qu'un seul nœud correct. Plus précisément, au moins un nœud correct parmi ceux qui proposent la valeur minimale ou la valeur maximale présente dans le réseau, doit recevoir suffisamment de messages (contrainte sur la quantité) contenants des valeurs supérieures ou inférieures (contrainte sur la la qualité). Bien entendu, les déplacements des nœuds doivent permettre à cette condition d'être remplie. Notre conclusion montre que la condition proposée peut être satisfaite si le nombre total de nœuds est plus grand que 3f +1