  By the distributed averaging problem is meant the problem of computing the
average value 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. Crafting a gossiping protocol which
accomplishes this is challenging because gossiping is an inherently
collaborative process which can lead to deadlocks unless careful precautions
are taken to ensure that it does not. Many gossiping protocols are
request-based which means simply that a gossip between two agents will occur
whenever one of the two agents accepts a request to gossip placed by the other.
In this paper, we present three deterministic request-based protocols. We show
by example that the first can deadlock. The second is guaranteed to avoid
deadlocks and requires fewer transmissions per iteration than standard
broadcast-based distributed averaging protocols by exploiting the idea of local
ordering together with the notion of an agent's neighbor queue; the protocol
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; a worst case bound on convergence
rate is provided.
