# Messy Broadcasting in Grid
## 1 Introduction  
Broadcasting in computer networking means the dissemination of information which is known initially only at some nodes to all network members. The goal is to inform every node in the minimal time possible. There are different models for broadcasting; the simplest and the original model is called the _classical model_. In the classical model, the dissemination happens in synchronous rounds under the constant communication time model, wherein a node may only inform one of its neighbors. This model remains popular not only for its history and graph-theoretical approach but also for its fastidious modeling of communications where small messages are exchanged, which is almost always the case in broadcasting. More information, good taxonomy, and how models are related to computer architecture are presented in [1, 2, 3, 4, 5]. The broadcast question is: What is the minimum number of rounds needed for broadcasting, and what broadcast scheme achieves it. In the classical model, however, for a network to know how to broadcast in minimum time, it is tacitly assumed that either:  
1. An omniscient being is coordinating the actions of the nodes;
2. Each node has a set of coordinated actions (or can compute it) optimized for each originator. In the latter case, the nodes must have enough storage space and must also be able to determine the originator. In many situations, these assumptions are not desirable or even realistic. For instance, the network designers may want the network topology to be independently expandable, or the use of high memory or processing power may not be desirable. Some reasons for the undesirability are increased financial cost, cybersecurity reasons, and even susceptibility to theft, etc. It is, therefore, natural that network nodes have local knowledge of the network rather than global knowledge. The exact models used in this paper were first defined in [6],named _messy models_. In these models, the nodes do not know the state of the network, the originator, or the start time of the broadcasting. Moreover, they are independent agents with no coordination and a limited view of their neighbors. There are three slightly different messy models:  
**Definition 1** (Model \(M_{1}\)). : _Each vertex knows the state of its neighbors at any time-unit, informed or uninformed. Each informed vertex must transmit the broadcast message to one of the uninformed neighbors, if any, in each time-unit._  
**Definition 2** (Model \(M_{2}\)). : _Every informed vertex knows from which neighbor (neighbors) it received the broadcast message and to which neighbors it has sent the message. Each informed vertex must transmit the broadcast message to all the neighbors except the ones it knows are informed._  
**Definition 3** (Model \(M_{3}\)). : _Each vertex knows to which neighbors it has sent the broadcast message. Each informed vertex must transmit the broadcast message to all the neighbors except the ones it knows are informed._  
With the local knowledge, it is not natural to ask about the minimum broadcast time, but rather it is natural to ask what is the worst-case time or broadcast scheme. **Definition 4** (Broadcast time of vertex \(u\)). : _The broadcast time of vertex \(u\) in graph \(G\) using model \(M_{i}\), denoted \(t_{i}(G,u)\) or simply \(t_{i}(u)\), for \(i=1,2,3\), is the **maximum** number of time-units required for a broadcast scheme originated from \(u\) to inform all the vertices._  
**Convention 1** (Impossible to broadcast). : _If it is impossible to broadcast from vertex \(u\) (for example, if the graph is disconnected), then conventionally \(t_{i}(u)=\infty\) for \(i=1,2,3\)._  
**Example 1**. : _Figure 1 provides an example and highlights the differences between the three messy models._  
**Definition 5** (\(t_{i}(u,\ v)\)). : _For \(i=1,2,3\), let \(t_{i}(G,\ u,\ v)\) or simply \(t_{i}(u,\ v)\), denote the maximum number of time-units required for a broadcast scheme originated from \(u\) in graph \(G\) to inform \(v\)._  
**Remark 1** (Usefulness of \(t_{i}(u,\ v)\)).