Convergence Speed in Distributed Averaging (Manisha Bhardwaj)

Reaching consensus and understanding the underlying convergence speed is one of the best studied problem in social network models and agent-based systems. Olshevsky and Tsitsiklis 2011 SIAM paper  describe many of the computational algorithms dealing with agreement and averaging formation on a communication network. The paper is focussed on analyzing already existing algorithms in the respective area and designing new efficient algorithms where consensus or agreement can lead to averaging algorithms with polynomial bounds on their resulting convergence rates.

Given a group of agents, each with its real-valued initial opinion in a communication network, influences its neighborhood opinion and hence every other agent in the network. These time-evolving opinions of all agents are expected to converge to the same point (average of initial opinions in case of averaging problem) provided each agent assigns appropriate weights to their neighborhood information (i.e. weights are entries of a stochastic matrix A) and also the dynamically evolving network is strongly connected. The convergence rate of such a process is solely determined by powers of matrix A in case of time-invariant communication network. Having an aperiodic and irreducible Markov chain determining the system in such a case is enough to guarantee convergence of such consensus algorithms. In order to have both agreement and averaging problem interleaved on an equal-neighbor, bidirectional graph, they proposed to run the agreement algorithm in parallel with two different initial opinions of every agent, one with scaled initial opinion by cardinality of the local neighborhood of each agent and other only depending on the latter condition of cardinality. The worst convergence time of such algorithm was shown to be O(n^3.

However, in case of dynamically evolving topology, the agreement or consensus algorithm is not polynomially bound as proved by Cao, Morse and Anderson. Olshevsky and Tsitsiklis in 2006  provided a remedy to such existing problem by proposing a “load-balancing algorithm” where agents share their initial load (or opinion) with their neighbors and try to equalize their respective loads (or opinions). Such an algorithm possess a polynomial bound on its convergence rate leading to a favorable performance.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s