# Messy Broadcasting in Grid
## 3 Study and Results on Messy Broadcasting
### Messy Model \(M_{3}\) in Infinite \(d\)-Dimensional Grid
The time it takes \(P\) to reach \(u^{1}\) is no more than \((d+1)\;d(u^{0},u^{1})\) time-units since each vertex in this portion of \(P\) has only \(d\) delay move options. Note that once \(P\) hits a border, it will remain on that border until it reaches \(v\) because of how an improving move is defined. Hitting the border means that for some \(i\), \(u_{i}^{1}=v_{i}\); without the loss of generality (by reindexing if necessary) assume \(u_{0}^{1}=v_{0}\). Now, let \(u^{2}\) be the first vertex that encounters a \(2\)-border. It may be the case that \(u^{2}=u^{1}\) if \(u^{1}\) is already on a \(2\)-border. The required time-units to travel from \(u^{1}\) to \(u^{2}\) on \(P\) are no more than \((d+2)\;d(u^{1},u^{2})\); one additional possible delay move for each vertex, which sends the message outside of \(G^{\prime}\) using the first coordinate. Similar to above, without the loss of generality, assume \(u_{1}^{2}=v_{1}\). Generally, let \(u^{k}\) for \(1\leq k\leq d\) be the first vertex that hits a \(k\)-border. The amount of time needed to go from \(u^{k-1}\) to \(u^{k}\) does not exceed \((d+k)\;d(u^{k-1},u^{k})\); maximum \(d+k-1\) delay moves before an improving move for each vertex on the path. Also, \(u_{k-1}^{k}=v_{k-1}\) is assumed. Consequently,  
\[t_{3}(0,v) = t_{3}(u^{0},u^{d})\leq\sum_{i=1}^{d}(d+i)\;d(u^{i-1},u^{i})\] \[= ((d+1)u_{0}^{1}-(d+1)u_{0}^{0})\] \[+((d+2)u_{1}^{2}-u_{1}^{1}-(d+1)u_{1}^{0})\] \[+((d+3)u_{2}^{3}-u_{2}^{2}-u_{1}^{1}-(d+1)u_{2}^{0})+\ldots\] \[+((d+d)u_{d-1}^{d}-u_{d-1}^{d-1}-\ldots-(d+1)u_{d-1}^{0})\] \[\leq (d+1)u_{0}^{1}+(d+2)u_{1}^{2}+\ldots+(d+d)u_{d-1}^{d}\] \[= (d+1)v_{0}+(d+2)v_{1}+\ldots+2 dv_{d-1}\]  
In the above argument, some reindexing has been performed for the ease of the explanation; therefore, the indices here are technically a permutation of \(0,1,\ldots,d-1\). This, then, tells us that without reindexing  
\[t_{3}(0,v)\leq\max_{\sigma}\left\{(d+1)v_{\sigma(0)}+(d+2)v_{\sigma(1)}+ \ldots+(2d)v_{\sigma(d-1)}\right\}\]  
where \(\sigma\) is a permutation of \(0,1,\ldots,d-1\). Hence, \(t_{3}(0,v)\leq(d+1)v_{\pi(0)}+(d+2)\;v_{\pi(1)}+\ldots+(2d)v_{\pi(d-1)}\), where \(\pi\) is a permutation that satisfies \(v_{\pi(0)}\leq v_{\pi(1)}\leq\ldots\leq v_{\pi(d-1)}\). The permutation \(\pi\) signifies that the border of a shorter dimension needs to be encountered sooner than a larger one. If, on the other hand, \(G^{\prime}\) is \(p\)-dimensional, where \(p<d\), the same argument as above can be made with \(u^{0}=u^{1}=\ldots=u^{d-p}\) in mind as if the broadcast is starting at \(u^{d-p}\) with \(2d-p\) delays available at the start. Like before, after each border is hit the number of delays available increases by one. Note that being in this case means that (again with reindexing in mind) \(v_{0}=v_{1}=\ldots=v_{d-p-1}=0\). Accordingly, the same expression as above will work here as well. An optimal scheme achieving this bound works as follows. Permutation \(\pi\) indicates an order on dimensions. Every vertex \(v\), after receiving the information, sends the information to the neighbors in the negative direction of dimensions by the order indicated by \(\pi\). After that, \(v\) uses the same order of dimensions and sends the information to the neighbors in their positive direction. It is easy to see that this scheme achieves the bound mentioned above. See Figure 3 for an example. For a general vertex \(v\), each coordinate may be negative. In this case, the argument remains largely the same, with a few minor nuances to consider. Firstly, in the definition of \(V^{\prime}\), the condition for each negative coordinate will change to \(v_{i}\leq w_{i}\leq 0\). Secondly, in the optimum scheme, which was described in two phases, the direction of message relay is reversed in both phases for every negative coordinate. Therefore, for any \(v\)  
\[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\}\]0  
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)}|\).