# Messy Broadcasting in Grid
## 3 Study and Results on Messy Broadcasting  
### Messy Model \(M_{3}\) in Infinite \(d\)-Dimensional Grid  
An infinite \(d\)-dimensional grid is a graph similar to the definition provided in Definition 6, with the distinction that each position in the \(d\)-tuple (also referred to as a coordinate) can take any integer value. As discussed in the introduction, in infinite graphs the broadcast time becomes meaningless and the focus of this section will be on finding \(t_{3}(0,\ v)\) for any vertex \(v\). Since there exists an automorphism that maps \(0\) to any other vertex, this analysis will be true for any broadcast originator. **Remark 2**. : _Our natural assumption is that in any broadcast scheme each informed vertex will inform all of its neighbors in consecutive time-units. If this is not the case, \(t_{3}(0,\ v)\) can be made arbitrarily long by choosing a path with that distance and considering a scheme that only follows that path or by simply increasing the idle time of the originator._  
Before diving into the details and discussions, it is helpful to provide some definitions that make describing the proof and the optimum scheme easier. First, consider the term \"improving/delaying move\". Under any scheme, each message relay is referred to as a \"_move_.\" If a move reduces the distance to vertex \(v\), we call it an \"_improving_\" move; otherwise, it is called a \"_delaying_\" move. Next, let us define a \(k\)-border. **Definition 8** (Saturated coordinate). : _For \(0\leq i\leq d-1\), the \(i\)th coordinate of vertex \(w\) is called saturated if \(w_{i}=v_{i}\)._  
**Definition 9** (\(k\)-border). : _A vertex \(w\) belongs to a \(k\)-border for some positive integer \(k\) if it has \(k\) saturated coordinates._  
According to Definition 9, any vertex in a \((k+1)\)-border is also in a \(k\)-border. For the sake of simplicity, a \(1\)-border is also referred to as a _border_. **Definition 10** (Improving path). : _Starting at \(0\), each broadcast scheme has a unique improving path that consists of the first encountered improving move for each of its vertices until it reaches \(v\)._  
Definition 10 is well-defined for the following reasons: Firstly, the degree of each vertex is \(2d\). Coupled with Remark 2 and the structure of a grid, this implies that for any vertex of this path except \(v\), there will be an improving move. Secondly, according to the definition of an improving move, vertex \(v\) is reached in exactly \(\sum_{i=0}^{d-1}v_{i}\) improving moves. Lastly, since the first improving move is always considered for each interior vertex, the path is unique. **Theorem 1** (Infinite grid, messy model \(M_{3}\)). : _Consider a \(d\)-dimensional infinite grid with \(0\) as the originator. Under messy model \(M_{3}\), for any vertex \(v\)_  
\[t_{3}(0,v)=\sum_{i=0}^{d-1}(d+i+1)(|v_{\pi(i)}|)\]  
_where \(\pi\) is a permutation of \(0,1,\ldots,d-1\) such that \(|v_{\pi(0)}|\leq|v_{\pi(1)}|\leq\ldots\leq|v_{\pi(d-1)}|\)._  
_An optimum scheme is also provided in the proof._  
Proof. : For the sake of simplicity, assume that all the coordinates of \(v\) are non-negative integers. Later, the general case will be justified. Consider an optimal scheme \(S\), and let \(P\) be the improving path based on \(S\). As discussed, \(P\) provides a valid route for information to be relayed from \(0\) to \(v\). Consequently, \(t_{3}(0,v)\) is less than or equal to the maximum time required for \(P\) to reach \(v\). Denote \(0\) with \(u^{0}\), and the distance of vertex \(x\) to \(y\) with \(d(x,\ y)\). Let \(G^{\prime}\) be a finite grid subgraph that is induced by the vertex set\[V^{\prime}=\left\{w\;\Big{|}\;w\in V(G),\;0\leq w_{i}\leq v_{i}\text{ for }0\leq i\leq d-1\right\}\]  
First, consider the case where \(G^{\prime}\) is \(d\)-dimensional; i.e., for every \(i\), \(v_{i}>u_{i}^{0}=0\). Let \(u^{1}\) be the first vertex on \(P\) that encounters a \(1\)-border (Definition 9) of \(G^{\prime}\); this should happen since \(u^{0}\) is on no border of \(G^{\prime}\) and \(v\) is the only vertex on the \(d\)-border.