Towards optimal convex combination rules for gossiping

By the distributed averaging problem is meant the problem of computing the average value y_avg of a set of numbers possessed by the agents in a distributed network using only communication between neighboring agents. Gossiping is a well-known approach to the problem which seeks to iteratively arrive at a solution by allowing each agent to interchange information with at most one neighbor at each iterative step. In the most widely studied situation, gossiping agents i and j update their current estimates x_i(t) and x_j(t) of y_avg by setting their new estimates x _i(t+1) and x_j(t+1) equal to the average of x _i(t) and x_j(t). A more general approach is for gossiping agents i and j to use the convex combination update rules x_i(t+1) = wx_i(t) + (1-w)x_j(t) and x_j(t + 1) = wx _j(t) + (1-w)x_i(t) respectively where w is a real number between 0 and 1. While for probabilistic gossiping protocols, a largest convergence rate is attained when w = 0.5, for deterministic gossiping protocols this is not the case. The aim of this paper is to demonstrate by computer experiments and analytically studied examples that for deterministic gossiping protocols which are periodic, the value of w which maximizes convergence rate is not necessarily w = 0.5 and moreover, convergence at the optimal value of w can be significantly faster than convergence at the value w = 0.5. Thus this paper's contribution is to provide clear justification for a deeper study of the optimum convergence rate question for gossiping algorithms using convex combination rules.