Majority Consensus by local polling
Moez Draief, Imperial College, UK
Abstract:
We consider a network where each of n anonymou) nodes holds some initial binary opinion. Our goal is to design efficient and fully-distributed algorithms that enable the network to reach a state where all the nodes hold the initial majority opinion. This problem has received a lot of interest from a number of communities such as distributed computing, communication networks, biological and chemical networks and social networks.
In this talk, I will present two distributed procedures for solving the majority consensus. In the first one we allow nodes to hold undecided states, provide a simple dynamics for solving the exact majority consensus problem on general connected graphs and derive bounds on the time to convergence of the algorithm. The second algorithm lets nodes interact with more than one neighbour at a time and show that, for some family of graphs of interest, and provided there is sufficient bias in the population towards the major it opinion, this algorithm solves majority consensus with high probability. We compute its asymptotic convergence time.
This is a joint work with M. Vojnovic and M. Abdullah.
Biography:Moez Draief graduated from the Ecole Polytechnique (Paris) in 2000. He then completed a DEA in Probability Theory at the University Paris VI. He undertook a PhD in the LIAFA (Theoretical Computer Science Group), University Paris VII.
From October 2004 to January 2007, he was a Marie Curie research fellow at the Statistical Laboratory and a lecturer in Part III (Certificate of Advanced Study in Mathematics), Cambridge University.
His research interests are: applied probability and discrete mathematics, queueing theory and stochastic networks, and the application of these to the analysis of distributed algorithms and complex networks such as Peer-to-Peer and ad hoc networks.