Friday April 16, 2010, 11.00-12.00, Room 3721, Lindstedtsvägen 25

Paolo Frasca
Politecnico di Torino

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