Florence Bénézit, EPFL

Location :

Ecole Normale Supérieure
en salle de réunion de l'équipe TREC,
entrée du bâtiment principal, escalier de la direction à gauche, 1ère porte au 2ème étage
45 rue d’Ulm
75005 Paris
http://www.di.ens.fr/AccesDI.html

Abstract :

Each node in a network makes a binary choice: it votes for A or B, Yes or No, 1 or 0... The goal of a distributed voting algorithm is to let every node in the network know the majority vote by means of local interactions only. 
We develop several voting algorithms which follow a classical setting:
 
- At any iteration, each node has a state, which was initialized with its vote.
- When communicating with its neighbors, a node updates its state according to its own state and its neighbors' states.
- The updating rule (also called automaton) should be the same for all nodes and it should not change with time.
- At convergence, every node should be able to deduce the majority vote from its state.
 
Previous work has systematically considered states of size 1 bit (0 or 1) although no solution was ever found in that case. 
Instead, our voting algorithm uses 2 bits states and it converges correctly in finite time with probability 1 in any connected network.
 
Several extensions of the 2 bits voting algorithm will be presented as well. 
First we present voting algorithms using states larger than 2 bits. 
Second we solve the multiple voting problem, where more than 2 candidates stand for election.

Host :

ENS