Moez Draief , Imperial College London

Location :

INRIA
salle de réunion « verte 2 »
5ème étage
23 AVENUE D'TALIE
75013 PARIS

 

Abstract :

(Joint work with M. Vojnovic) 

We consider the speed of convergence of an instance of the binary interval consensus, a 
distributed and decentralized algorithm for computing the quantized average value. With 
binary consensus problem, each node initially holds one of two states and the goal for each node 
is to correctly decide which one of the two states was initially held by the majority of nodes. 

We derive an upper bound on the expected 
convergence time that holds for arbitrary connected graphs; it is based on the location of the 
eigenvalues of some contact rate matrices. We instantiate our bound for particular networks of 
interest, including complete graphs, star-shaped networks, and Erdos-Renyi random graphs, and in 
the former two cases compare with alternative computations. We find that for all these examples 
our bound is of the exact order with respect to the number of nodes and in some cases yields the 
exact multiplicative constant. We pinpoint the fact that the expected convergence time critically 
depends on the voting margin defined as the difference between the proportions of nodes that 
initially held the majority and the minority states, respectively. We derive an exact relation between 
the expected convergence time and the voting margin, for some of these graphs, that reveals how 
the expected convergence time tends to infinity as the voting margin approaches zero.  

 
Our results provide insights on how the expected convergence time depends on the network 
topology which can be used for performance evaluation and network design. The results are of 
interest in the context of peer-to-peer systems; in particular, for sensor networks and distributed 
databases.

Host :

INRIA