In this talk we consider a class of distributed algorithms known as gossip algorithms for information propagation in arbitrary connected networks. Distributed algorithms of this kind have applications to peer-to-peer, sensor, and ad hoc networks, in which nodes operate under limited computational and communication resources.
We analyze the information propagation problem under the local communication constraint and the relation between the information propagation time and the isoperimetric properties of the underlying graph. This characterization leads to the problem of finding the fastest information propagation algorithm formulated as a concave maximization problem over the convex set of graph-conformant doubly stochastic matrices.
The analysis of the scheme shows that it is not only capacity achieving, but the propagation of the information entities through the network carrying innovative information follow the propagation model of jobs through a queueing network and thus, fluid flow models give good approximations. We seek to find the asymptotic rate optimality of a scheme that it is considered as the prototype for a family of related and improved schemes (LT codes, Raptor codes, on-line codes, RT oblivious erasure correcting codes, greedy random scheme codes). Using various degrees of feedback, lower decoding complexity or low memory usage can be achieved.