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).