Optimization and Systems Theory Seminar
Friday April 16, 2010, 11.00-12.00, Room 3721, Lindstedtsvägen 25

Paolo Frasca  Politecnico di Torino

Broadcast gossip averaging algorithms: interference and asymptotical error

In this talk we present two related iterative randomized algorithms for distributed computation of averages. The first one is the recently proposed Broadcast Gossip algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel asynchronous version of the previous one, in which at each iteration every node possibly broadcasts, with a given probability: thus the latter algorithm is affected by interference among messages. A mean square analysis is performed, under the assumption of suitable symmetries in the network topology. Both algorithms are proved to converge and their performance is evaluated in terms of rate of convergence and asymptotical error. We highlight the role of the graph topology and the effects of the design parameters on the performance, focusing on the behavior for large networks. In particular, we prove that on sparse graphs with bounded degree, both algorithms are asymptotically unbiased, in the sense that the asymptotical errors go to zero as the network grows larger.

Calendar of seminars Last update: March 3, 2010.