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