Gossiping problem

Gossiping problem --- задача распространения слухов.

The gossiping problem is the problem of information dissemination described in a group of individuals connected by a communication network. In gossiping, every node knows a piece of information and needs to transmit it to anyone else. This is achieved by placing communication calls over the communication lines of the network. It is assumed that a node can communicate with at most one of its neighbors at any given time, and a communication between two nodes takes one unit of time. This model implies that we will deal with connected graphs without loops and multiple edges to model the communication network. Note also that, depending on their cases, we will either consider a half-duplex or a full-duplex model. In the latter, when communication takes place along a communication line, the information flows in both directions, while in the former only one direction is allowed. Hence, in the half-duplex model, we will deal with directed graphs, while we will consider undirected graphs in the full-duplex model.

See also

• Broadcasting problem.