Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping, every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting, one individual has an item of information which needs to be communicated to everyone else (Hedetniemi et al. 1988).

A popular formulation assumes there are n people, each one of whom knows a scandal which is not known to any of the others. They communicate by telephone, and whenever two people place a call, they pass on to each other as many scandals as they know. How many calls are needed before everyone knows about all the scandals? Denoting the scandal-spreaders as A, B, C, and D, a solution for n=4 is given by {A,B}, {C,D}, {A,C}, {B,D}. The n=4 solution can then be generalized to n>4 by adding the pair {A,X} to the beginning and end of the previous solution, i.e., {A,E}, {A,B}, {C,D}, {A,C}, {B,D}, {A,E}.

Gossiping (which is also called total exchange or all-to-all communication) was originally introduced in discrete mathematics as a combinatorial problem in graph theory, but it also has applications in communications and distributed memory multiprocessor systems (Bermond et al. 1998). Moreover, the gossip problem is implicit in a large class of parallel computing problems, such as linear system solving, the discrete Fourier transform, and sorting. Surveys are given in Hedetniemi et al. (1988) and Hromkovic et al. (1995).

Let f(n) be the number of minimum calls necessary to complete gossiping among n people, where any pair of people may call each other. Then f(1)=0, f(2)=1, f(3)=3, and


for n>=4. This result was proved by (Tijdeman 1971), as well as many others.

In the case of one-way communication ("polarized telephones"), e.g., where communication is done by letters or telegrams, the graph becomes a directed graph and the minimum number of calls becomes


for n>=4 (Harary and Schwenk 1974).

See also

Broadcast Time, Graph Bandwidth

This entry contributed by Ronald M. Aarts

Explore with Wolfram|Alpha


Bermond, J.-C.; Gargano, L.; Rescigno, A. A.; and Vaccaro, U. "Fast Gossiping by Short Messages." SIAM J. Comput. 27, 917-941, 1998.Harary, F. and Schwenk, A. J. "The Communication Problem on Graphs and Digraphs." J. Franklin Inst. 297, 491-495, 1974.Hedetniemi, S. M.; Hedetniemi, S. T.; and Liestman, A. L. "A Survey of Gossiping and Broadcasting in Communication Networks." Networks 18, 319-349, 1988.Hromkovic, J.; Klasing, R.; Monien, B.; and Peine, R. "Dissemination of Information in Interconnection Networks (Broadcasting and Gossiping)." In Combinatorial Network Theory (Ed. F. Hsu and D.-A. Du). Norwell, MA: Kluwer, pp. 125-212, 1995.Tijdeman, R. "On a Telephone Problem." Nieuw Arch. Wisk. 19, 188-192, 1971.

Referenced on Wolfram|Alpha


Cite this as:

Aarts, Ronald M. "Gossiping." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein.

Subject classifications