<p>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?</p>

<p>Edit: never mind, this doesn't work. On the complete graph all the nodes would end up mostly retransmitting the same popular messages and many messages would never be received by any node other than the source. Maybe it would help if the nodes prefer to transmit messages they've received less frequently?</p>

CC BY-SA 2.5
2010-10-25T15:08:53.540Z
2010-10-25T22:18:41.397Z
2010-10-25T22:18:41.397Z
Warren Schudy
<p>I think the reference you are looking for is the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.317&amp;rep=rep1&amp;type=pdf">paper</a> "Broadcasting algorithms in radio networks with unknown topology" by Czumaj and Rytter.  It seems <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.1296&amp;rep=rep1&amp;type=pdf">this paper</a> makes some improvements, but I think it depends on the specifics of the model.</p>

CC BY-SA 2.5
2010-10-25T16:34:33.137Z
Yes, this is the paper I was looking for. Thank you !
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-25T14:48:31.447Z
2010-10-25T14:48:31.447Z
Lev Reyzin
<p>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.</p>

<p>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).</p>

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

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

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-25T11:46:50.527Z
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...
Jukka Suomela
CC BY-SA 2.5
2010-10-25T12:39:04.113Z
Oups, forgot to mention about that, I edited accordingly.
Sylvain Peyronnet
CC BY-SA 2.5
2010-10-25T14:46:44.673Z
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?
Warren Schudy
CC BY-SA 2.5
2010-10-25T14:49:50.070Z
Can nodes tell the difference between a collision and no one transmitting?
Warren Schudy
CC BY-SA 2.5
2010-10-25T14:54:09.470Z
Is the connections graph an arbitrary strongly connected directed graph?
Warren Schudy
<reference-request><dc.distributed-comp>
complexity of randomized gossiping
Sylvain Peyronnet
# complexity of randomized gossiping

(Asked by: username_0 on 2010-10-25)

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.

**Tags:** reference-request, dc.distributed-comp
> **Comments:**
> **username_1**: 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...  
> **username_0**: Oups, forgot to mention about that, I edited accordingly.  
> **username_2**: 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?  
> **username_2**: Can nodes tell the difference between a collision and no one transmitting?  
> **username_2**: Is the connections graph an arbitrary strongly connected directed graph?  

---

## 2 answers

### Answer by username_3 on 2010-10-25. Score: 11 | Accepted answer

I think the reference you are looking for is the [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.317&rep=rep1&type=pdf) "Broadcasting algorithms in radio networks with unknown topology" by Czumaj and Rytter. It seems [this paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.1296&rep=rep1&type=pdf) makes some improvements, but I think it depends on the specifics of the model.

> **Comments:**
> **username_0**: Yes, this is the paper I was looking for. Thank you !  

---

### Answer by username_2 on 2010-10-25. Score: 0

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?

Edit: never mind, this doesn't work. On the complete graph all the nodes would end up mostly retransmitting the same popular messages and many messages would never be received by any node other than the source. Maybe it would help if the nodes prefer to transmit messages they've received less frequently?


---

