Skip to Main content Skip to Navigation

Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks

Chuanyou Li 1 Michel Hurfin 2 Yun Wang 1
2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Michel Hurfin Connect in order to contact the contributor
Submitted on : Thursday, May 31, 2012 - 8:19:28 PM
Last modification on : Tuesday, October 19, 2021 - 11:58:54 PM
Long-term archiving on: : Thursday, December 15, 2016 - 10:18:00 AM


Files produced by the author(s)


  • HAL Id : hal-00703111, version 1
  • ARXIV : 1206.0089


Chuanyou Li, Michel Hurfin, Yun Wang. Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks. [Research Report] RR-7985, INRIA. 2012, pp.17. ⟨hal-00703111⟩



Record views


Files downloads