## 3 Study and Results on Messy Broadcasting
### Messy Broadcasting in Grid
#### 3.2.2 Model \(M_{3}\)
: _Let \(v=(i,j)\) be a border vertex, then_  
\[t_{3}(0,v)\leq \begin{cases}0&i=0\ and\ j=0\\ 2+3(j-1)&i=0\ and\ 0<j\leq\ m\\ 1+3(i-1)&j=0\ and\ 0<i\leq\ n\\ 1+3(n-1)+2+3(j-1)&i=n\ and\ 0<j\leq\ m\\ 2+3(m-1)+2+3(i-1)&j=m\ and\ 0<i\leq n\end{cases} \]  
A comparison between the maximum time of the two border-creeping paths \(P_{1}\) and \(P_{2}\) separates the vertices into two groups: the vertices whose \(P_{1}\) maximum time is less than equal to that of \(P_{2}\), and the rest. The boundary is a line; let us denote it with \(L(P_{1},\ P_{2})\). The equations associated with each of these six lines are as follows. \[L(dr,\ rd): i=j-1\] \[L(dr,\ dru): i=n-\left(\frac{j+1}{7}\right)\] \[L(rd,\ rdl): i=7 nt-7j-1\] \[L(dru,\ rdl): i=(n-m)+j-\frac{1}{7}\] \[L(rd,\ dru): i=\frac{7 nt-2}{8}\] \[L(dr,\ rdl): j=\frac{7m}{8}\]  
Figure 4 shows an example and also explains how to detect the regions where a particular path has the minimum. For better visualization of these regions and for the analysis to come, it is helpful to note the common intersections of some of these lines, as outlined in Lemma 4. **Lemma 4** (Common intersections). : _Each of the following four groups of three lines has a common intersection._  
1. \(\left\{L(dr,\ rd),\ L(dr,\ dru),\ L(rd,\ dru)\right\}\) _3. \(\left\{L(dru,\ rdl),\ L(dr,\ dru),\ L(dr,\ rdl)\right\}\) _4. \(\left\{L(dr,\ rd),\ L(rd,\ dru)\right\}\)_  
Proof. : The common point for group 1 is \(\left(\frac{7 nt-2}{8},\ \frac{7 nt+6}{8}\right)\), for group 2 is \(\left(\frac{7 nt-2}{8},\ m-\frac{nt+6/7}{8}\right)\), for group 3 is \(\left(n-\frac{m}{8}-\frac{1}{7},\ \frac{7m}{8}\right)\), and for group 4 is \(\left(\frac{7m}{8}-1,\ \frac{7m}{8}\right)\). Having established an upper bound, our next step is determining a lower bound by devising an appropriate scheme. For a given scheme \(S\), let \(t_{S}(v)\) be the time for \(S\) to inform \(v\) for the first time. By definition, \(t_{3}(0,v)=\max_{S}\{t_{S}(v)\}\) for all schemes \(S\). For any vertex \(v\), let \(x(v)\in\{dr,\ dru,\ rd,\ rdl\}\) be the type of border-creeping path which achieves the upper-bound based on Lemmas 2 and 3. In any scheme \(S\), if \(t_{S}(v)=t_{x(v)}(v)\), the behavior of \(S\) throughout the \(x(v)\)-path is uniquely determined. This is because only one behavior causes the vertices of the \(x(v)\)-path to delay the information to \(v\) for this duration, and any other behavior will inform \(v\) sooner. With this understanding, we investigate whether there exists a scheme \(S\) such that for any vertex \(v\), \(t_{S}(v)=t_{x(v)}(v)\). If such a scheme exists, it would be an optimum scheme. Unfortunately, for large enough \(n\) and \(m\), such a scheme cannot exist. This is because the final branch-out behavior is explicitly tailored to the target vertex \(v\). If vertices \(v\) and \(u\) share a common segment of their border-creeping paths, this will result in conflicting behavior. For example, consider a grid with \(n\geq 2\) and \(m\geq 2\). In this case, \(x((1,1))=x((2,1))=dr\). The \(dr\)-path for \((2,1)\) shares the \(dr\)-path for \((1,1)\) until vertex \((1,0)\). The requirements of the described unique behavior for vertex \((1,0)\) differ depending on which of these two vertices is being considered. Therefore, such a scheme \(S\) cannot exist. However, if we relax the behavioral requirements for this final branching, we can devise a scheme we call the _border-evading scheme_. **Border-evading scheme**. This scheme behaves as follows: For any border vertex \(v\), the behavior of the path informing \(v\) is dictated by the \(x(v)\)-path informing \(v\) in \(t_{x(v)}(v)\) time-units. For any interior vertex \(v\), consider the unique behavioral requirement to achieve \(t_{x(v)}(v)\) as described above. At the point of final branching, the requirement is to first send the message to the previous sender on the border, then to the next vertex on the border, and lastly toward \(v\) when branching out.