13
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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... $\endgroup$
    – Jukka Suomela
    Commented Oct 25, 2010 at 11:46
  • $\begingroup$ Oups, forgot to mention about that, I edited accordingly. $\endgroup$
    – Sylvain Peyronnet
    Commented Oct 25, 2010 at 12:39
  • $\begingroup$ 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? $\endgroup$
    – Warren Schudy
    Commented Oct 25, 2010 at 14:46
  • $\begingroup$ Can nodes tell the difference between a collision and no one transmitting? $\endgroup$
    – Warren Schudy
    Commented Oct 25, 2010 at 14:49
  • $\begingroup$ Is the connections graph an arbitrary strongly connected directed graph? $\endgroup$
    – Warren Schudy
    Commented Oct 25, 2010 at 14:54

2 Answers 2

Reset to default
11
$\begingroup$

I think the reference you are looking for is the paper "Broadcasting algorithms in radio networks with unknown topology" by Czumaj and Rytter. It seems this paper makes some improvements, but I think it depends on the specifics of the model.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, this is the paper I was looking for. Thank you ! $\endgroup$
    – Sylvain Peyronnet
    Commented Oct 25, 2010 at 16:34
0
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.