## 3 Study and Results on Messy Broadcasting
### Messy Broadcasting in Grid
#### 3.2.2 Model \(M_{3}\)  
The presence of borders makes the problem much more complex than the analysis in Section 3.1. It is worth noting that in this section the use of the word \"border\" is similar but different from that in Definition 9. Here, in addition to a saturated coordinate (Definition 8), a \(0\) coordinate is also considered to define a \(k\)-border aligning with the usual intuition. Unlike in an infinite grid, the maximum possible delay any \(k\)-border vertex could cause is smaller than that of \((k-p)\)-border vertices, where \(p>0\). This section provides the optimum broadcast time and an optimum broadcast scheme for a two-dimensional grid \(G[n+1,\ m+1]\) for some integers \(n\geq 1\) and \(m\geq 1\). By symmetry, without the loss of generality, assume \(n\leq m\). Intuitively, since the interior vertices may cause more delays, it is implied that there is an optimum broadcast scheme where, for any vertex \(v\), the path that first informs \(v\) creeps through the borders first until it branches out in a straight line to reach \(v\). Based on this intuition, _border-creeping paths_ are defined, which will be the cornerstone of our analysis. **Definition 11** (Border-creeping paths). : _Inspired by the above motivation, for a vertex \(v\), consider the following four border-creeping paths: dr-path, dr-path, rd-path, and rd-path. For example, dr-path starts at \(0\), creeps the border downward until it reaches the bottom border, then goes right on the bottom border until it reaches the horizontal position of \(v\), and finally, it goes up (not necessarily on any border) until \(v\) is reached. The last change in direction is the only part of these paths that may not be on any border._  
Other border-creeping paths, such as the \(drul\)-path, are not considered since they are slower than another defined border-creeping path, which in this case would be the \(rdl\)-path. **The first move. ** Which direction should the originator \(0\) send the message first? Our intuition tells us that the shorter dimension (\(n\), the vertical) should be informed first. The reason is as follows: As discussed, the bottleneck for delays is the borders; therefore, the optimum scheme should delay informing them as much as possible. If the message is sent through the shorter dimension first, while it is true that the shorter border will be informed sooner, it is also true that it delays the progression of information toward the longer dimension (to the right) with the help of interior vertices and the fact that the bottom border already has a significant enough delay. Based on this intuition, _assume_ that the first move is downward along the shorter dimension. Later, we will prove that this is an optimum choice. Based on the first move assumption, it is easy to see that for an interior vertex \(v=(i,j)\) the maximum time it takes each border-creeping path to reach \(v\) is \[t_{dr}(v) =1+3(i-1)+3+4(j-1)\] \[t_{drn}(v) =1+3(n-1)+2+3(j-1)+3+4(n-i-1)\] \[t_{rd}(v) =2+3(j-1)+3+4(i-1)\] \[t_{rdl}(v) =2+3(m-1)+3+3(i-1)+3+4(m-j-1)\]  
For example, let us investigate the \(dru\)-path. The \(1\) is the maximum time it will take to reach the vertex one down from \(0\) (originator), the \(3(n-1)\) the time to reach the bottom border, the \(2\) for changing the direction at the corner vertex and going one to the right, the \(3(j-1)\) to reach the horizontal position of \(v\), the \(3\) to change the direction upward and going one up, and the \(4(n-i-1)\) to go up and reach \(v\). See the relevant portion of the scheme in Figure 4. These values give an easy upper bound to \(t_{3}(0,v)\) for interior vertices. Figure 4: Broadcasting under messy model \(M_{3}\) in \(G\)[17; 21]. **Lemma 2** (Upper-bound, interior vertices). : _Let \(v=(i,j)\) be an interior vertex, then_  
\[t_{3}(0,v)\leq\min\{t_{dr}(v),\ t_{dru}(v),\ t_{rd}(v),\ t_{rdl}(v)\}\]  
A similar upper bound can be given to border vertices as well; here, however, it is clear which border-creeping path has the minimum time. **Lemma 3** (Upper-bound, border vertices).