In classical broadcasting, all vertices are required to have knowledge of the network topology, the originator of the broadcast, and the time at which the broadcast began. Although such knowledge makes efficient communication possible through the use of coordinated broadcast protocols, it is not always available in practice.

In 1994, Ahlswede, Haroutunian, and Khatchatrian [1] introduced a broadcasting variant called messy broadcasting. In this type of broadcasting, every vertex acts independently, without knowing the message originator or the time at the which message was sent, and has very limited knowledge of the network's topology; that is, all informed vertices broadcast to randomly-chosen neighbours at each time unit.

In [1], the researchers introduced the following three models for messy broadcasting:

Model  M₁: At each unit of time, every vertex knows the state of each of its neighbours: informed or uninformed. In this model, each informed vertex must transmit the broadcast message to one of its uninformed neighbours, in any, in each time unit.

Model  M₂: Every informed vertex knows from which vertex (vertices) it received the broadcast message and to which neighbours it has sent the message. Thus, it knows that this vertex (or these vertices) are informed. In this model, each informed vertex must transmit the broadcast message to one of its neighbours other than the ones that it knows are informed, if any, in each time unit.

Model  M₃: Every informed vertex knows to which neighbours it has sent the message. In this model, each informed vertex must transmit the broadcast message to one of its neighbours to which it has not yet sent the message, if any, in each time unit.

The broadcast time of vertex u in a graph G using model M_i, denoted t_i, 1 £ i £ 3, is defined to be the maximum number of time units required to inform all vertices of G when u is the originator of the messy broadcast. We then define the broadcast time of the graph G as t_i(G) = max {t_i(u) | u Î V(G)}. Research in messy broadcasting concentrates on finding t_i(G) for different graphs G. The goal is to find graphs with the smallest messy broadcast times possible.

An important difference between classical and messy broadcasting is that while classical broadcast schemes can be represented by trees, messy broadcast schemes must be represented by digraphs. In the case of model M₁, the digraphs will be acyclic; in the case of the other two models, the digraphs may contain cycles, as shown below:

Let G be a graph on n vertices. Proving that t_i(G) = f (n) is a two-step process. First, one must demonstrate a messy broadcast scheme taking f (n) time units; hence showing that t_i(G) ³ f (n). Second, one must demonstrate that no messy broadcast in G can take more than f (n) time units; this shows that t_i(G) £ f (n), completing our proof that t_i(G) = f (n).

In 1998, Harutyunyan and Liestman proved that t₁(K_n) = t₂(K_n) = t₃(K_n) = n - 1 [8]. We assume, without loss of generality, that the vertices of K_n are numbered 0,1, ..., n - 1 and that vertex 0 is the originator. A scheme possible in all three models is for all informed vertices to call vertex i at time i. This shows that t_i(K_n) ³ n - 1 for all i. The observation that the originator must call its n - 1 neighbours in times 1,2, ..., n - 1 shows that no messy broadcast in K_n can take more than n - 1 time units, hence completing our proof.