The gossip problem (telephone problem) is an information dissemination problem where each of $n$ nodes of a communication network has a unique piece of information that must be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. Upon a call between the given two nodes, they exchange the whole information known to them at that moment.

The minimum number of calls needed to guarantee the spread of whole information is $2n-4$. http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf

Assuming that the calls between non-overlapping pairs of nodes can take place simultaneously, the minimum amount of time $T(n)$ required to complete gossiping is $\lceil \log_2 n \rceil$ for even $n$ and $\lceil \log_2 n \rceil + 1$ for odd $n$. http://onlinelibrary.wiley.com/doi/10.1002/net.3230180406/abstract

As it is written in the paper by R. Labahn, "Kernels of minimum size gossip schemes", Discrete Mathematics 143 (1995) 99-139:

Theorem 5.3 Any gossip scheme on $n \geq 4$ vertices with $2n-4$ calls has at least $2\lceil \log_2 n \rceil - 3$ rounds.

My question is following. Is there a result on the problem to find the minimum number of calls of a gossip scheme with time (rounds) $T(n)$.

  • $\begingroup$ It looks like your own paper has such results. $\endgroup$ Dec 4, 2013 at 23:05
  • $\begingroup$ @BrianRushton, thank you for the comment. Which paper you mean ? $\endgroup$ Dec 4, 2013 at 23:58
  • $\begingroup$ It was this one:arxiv.org/abs/1304.5633 but I didn't read the second half of the title. Are you looking for a reference to add to your paper? $\endgroup$ Dec 5, 2013 at 0:16
  • $\begingroup$ Yes, this paper is about fault-tolerance of the gossip schemes. I have some ideas, and I want simply find any results about minimum number of calls of a gossip scheme with minimal time $T(n)$ to develop the theory. Presumably it is an open question. $\endgroup$ Dec 5, 2013 at 9:19


You must log in to answer this question.

Browse other questions tagged .