Many information dissemination problems are studied in connection with networks and computer science. Broadcasting is one such problem. In this problem, one node of a communication network must transmit a message to all other nodes in the network. The communication network is modelled as a graph or digraph.
Briefly, consider two common topologies for local area networks (LANs): buses and rings. A bus can be modelled in graph-theoretic terms by a path Pn on n vertices, and a ring can be modelled by a cycle on n vertices, Cn. Questions about network topology are, in general, answered by graph theory. In this area of theoretical computer science, we use techniques from graph theory to construct optimum network topologies.
Formally, let G = (V,E) (or D = (V,E), in the case of a digraph), and let u Î V(G) (or V(D)) be the originator of the broadcast. When broadcasting begins, the originator is the only informed vertex. During each unit of time, each informed vertex calls one uninformed adjacent vertex. Vertices may make only one call per time unit, but may receive from any number of vertices in the same time unit. Each call takes exactly one unit of time. Broadcasting is completed when all vertices are informed. The set of all calls made in the broadcast is called the broadcast protocol or broadcast scheme.
Most work on the subject has been on classical broadcasting, in which every vertex of the graph is assumed to broadcast using an optimal scheme. Research in classical broadcasting focuses on the construction of broadcast graphs, in which any originator can broadcast in élog2nù time. Of particular interest is the function B(n), the minimal number of edges in a broadcast graph on n vertices. A minimum broadcast graph (mbg) is a graph on n vertices having B(n) edges; since edges represent communication lines, these graphs represent the cheapest possible communication networks. Classical broadcasting requires all vertices to have knowledge of the network topology, the originator of the message, and the time at which the message was sent.
Research has also been done on graphs that are not broadcast graphs, that is, graphs in which broadcasting requires more than élog2nù time units. Sometimes, as in the case of de Bruijn graphs, trees, and grids, this is because these graphs have desirable properties, such as regularity or simplicity. At other times, research is motivated by the desire to create fault-tolerant networks, in which efficient broadcasting can be accomplished even if lines fail. Other variants of broadcasting include messy broadcasting and k-broadcasting.
Topics in broadcasting covered on this site include:
