Gossiping

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  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 , , , and , a solution for  is given by , , , . The  solution can then be generalized to  by adding the pair  to the beginning and end of the previous solution, i.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  be the number of minimum calls necessary to complete gossiping among  people, where any pair of people may call each other. Then , , , and

for . 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  (Harary and Schwenk 1974).

REFERENCES

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.