# complexity of randomized gossiping

The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes.

Now, my question is in the context of the ad-hoc network model (we assume that a node does not have any prior knowledge about the topology of the network, its in and out degrees, and the set of its neighbours. In fact the only knowledge of each node is its own identifier and the total number of nodes).

I also assume that all nodes have access to a global clock and work synchronously in discrete time steps called rounds.

The complexity of an algorithm in this context is the number of rounds needed for completion.

I remember that there exists an algorithm that solves the gossiping problem in $O(n \log ^2 n)$ rounds with high probability. But I cannot find the reference anymore, and I am wondering if there are more recent results on that matter.

edit following the judicious comment: at each round a node can transmit the message to all its neighbours and can receive the messages from them. A node will receive a message at a given round if and only if exactly one of its neighbours transmits at that round. Otherwise a collision occurs and none of the messages is received by the node.

• I guess you are assuming that in each round each node can send a message to only one neighbour? Otherwise the problem is trivial to solve in $O(n)$ rounds... Oct 25, 2010 at 11:46
• Oups, forgot to mention about that, I edited accordingly. Oct 25, 2010 at 12:39
• If a node $v$ has received messages $m_u$ and $m_w$ can it transmit $\{m_v,m_u,m_w\}$ in a single round or are transmitted messages limited to the size of one payload only? Oct 25, 2010 at 14:46
• Can nodes tell the difference between a collision and no one transmitting? Oct 25, 2010 at 14:49
• Is the connections graph an arbitrary strongly connected directed graph? Oct 25, 2010 at 14:54

How about the following algorithm: at round number $t$ every node transmits with probability $2^{-(t \mod \log n)}$, and chooses the message to transmit uniformly at random from among the messages it has received so far. Might that work?