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$ – Brian Rushton Dec 4 '13 at 23:05
  • $\begingroup$ @BrianRushton, thank you for the comment. Which paper you mean ? $\endgroup$ – Vahagn Poghosyan Dec 4 '13 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$ – Brian Rushton Dec 5 '13 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$ – Vahagn Poghosyan Dec 5 '13 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.