Revisiting request-based gossiping: The effects of queue updates on convergence time

Gossiping is a well-known approach to the distributed averaging problem whose purpose is to enable the members of a group of autonomous agents to iteratively determine the average of their initial scalar-valued gossip variables by allowing each agent to interchange information with at most one neighbor at each iterative step. In prior work we presented a deterministic request-based gossiping protocol which is guaranteed to avoid deadlocks and requires fewer transmissions per iteration than broadcast-based distributed averaging protocols by exploiting the ideas of local ordering and neighbor queues [1]. The aim of this paper is to investigate the effects of queue updates on the convergence and convergence time of request-based gossiping. Three gossiping protocols with different types of queue updates are presented. We show by example that the first protocol can deadlock. The second protocol is guaranteed to converge exponentially fast and requires the simplest queue updates, which provides an in-depth understanding of how local ordering and queue updates avoid deadlocks. It is shown that a third protocol which uses a slightly more complicated queue update rule can lead to significantly faster convergence.