Florence Bénézit | EPFL Graph Search

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

The Distributed Multiple Voting Problem

Martin Vetterli, Patrick Thiran, Florence Bénézit

A networked set of agents holding binary opinions does not seem to be able to compute its majority opinion by means of local binary interactions only. However, the majority problem can be solved using two or more bits, instead of one [1]. Pairs of agents asynchronously exchange their states and update them according to a voting automaton. This paper presents binary voting automata as well as solutions to the multiple voting problem, where agents can vote for one candidate among |C| >= 2 candidates and need to determine the majority vote. The voting automata are derived from the pairwise gossip algorithm, which computes averages. In the binary case (|C| = 2), we focus on averages in dimension 1, but in the multiple case (|C| >= 2) we quantize gossip in dimension |C | - 1, which is larger than or equal to 1. We show in particular that a consensus on majority can be reached using 15 possible states (4 bits) for the ternary voting problem, and using 100 possible states (7 bits) for the quaternary voting problem.

2011

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Martin Vetterli, Patrick Thiran, Florence Bénézit

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

IEEE2010

Order-Optimal Consensus Through Randomized Path Averaging

Martin Vetterli, Patrick Thiran, Florence Bénézit

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust mes- sage-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wire- less ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding ( O(n^2) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a n^1/2 factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional n^1/2 factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high prob- ability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algo- rithms operating over various graph topologies.

Institute of Electrical and Electronics Engineers2010