## 3 Framework
### Overhead Reduction and Properties of SERENA
#### 3.5.1 Overhead Reduction
_Property P0: With assumptions \(A0\) to \(A2\), in three-hop coloring and tree coloring, any node \(N\) can color itself if and only if \(Prio(N)=max(Maxprio1(N),Maxprio2(N),Maxprio3(N))\), with:_  
\(Maxprio1(N)=max_{M\in{\rm{hop}}(N)}(Prio(M)\ with\ M\ uncolored)\)_,_  
\(Maxprio2(N)=max_{M\in{\rm{hop}}(N)}(Maxprio1(M))\)_,_  
\(Maxprio3(N)=max_{M\in{\rm{hop}}(N)}(Maxprio2(M))\) _in the general case,_  
\(Maxprio3(N)=max_{M\ parent\ or\ child\ of\ N}(Maxprio Send2(M))\) _in the tree case, where_  
\(MaxprioSend2(N)=max_{M\in{\rm{hop}}(N)}(Maxprio1(M)=Prio(P)\) _where \(P\) is a parent or child of \(M)\)._  
_Proof:_ With three-hop coloring and tree coloring, any node \(N\) can color itself if and only if no uncolored node in \(\mathcal{N}(N)\) has a priority higher than \(N\). We recall that two different nodes never have the same priority insofar as ties are broken by node identifiers that are assumed unique in the considered network. Let us show that if any node \(N\) is coloring itself, then  
\(Prio(N)=max(Maxprio1(N),Maxprio2(N),Maxprio3(N))\). If node \(N\) is coloring itself, it means that:  
* all its uncolored one-hop neighbors have a smaller priority. Hence, for any \(M\) uncolored one-hop neighbor of \(N\), we have \(Prio(M)<Prio(N)\). Hence, \(Maxprio1(N)=max_{M\in{\rm{hop}}(N)}(Prio(M)\ for\ M\ uncolored)<Prio(N)\);
* all its uncolored two-hop neighbors have a smaller priority. \(Maxprio2(N)\) is the maximum priority of uncolored nodes \(P\) that are one-hop neighbors of \(M\), any one-hop neighbor of \(N\). Consequently, we have the following cases:
* node \(P\) is the node \(N\) itself and has priority \(Prio(N)\);
* \(P\) is a one-hop or two-hop neighbor of node \(N\). In which case, we have by assumption: \(Prio(P)<Prio(N)\). Hence, \(Maxprio2(N)=Prio(N)\). * and all its uncolored three-hop neighbors in \(\mathcal{N}(N)\) have a smaller priority. * In the general coloring, \(Maxprio3(N)\) is the maximum priority of uncolored nodes \(Q\) that are one-hop neighbors of \(P\), itself one-hop neighbor of \(M\), one-hop neighbor of \(N\). Consequently, we have the following cases:
* node \(Q\) is the node \(N\) itself and has priority \(Prio(N)\);
* \(Q\) is a one-hop, two-hop or three-hop neighbor of node \(N\). In which case, we have by assumption: \(Prio(Q)<Prio(N)\). Hence, \(Maxprio3(N)=Prio(N)\). * In the tree coloring, \(Maxprio3(N)\) is the maximum priority of uncolored nodes \(Q\) that are parent or child of \(P\), itself one-hop neighbor of \(M\) a parent or child of \(N\). We then have the following cases:
* node \(Q\) is the node \(N\) itself and has priority \(Prio(N)\);
* \(Q\) is a one-hop or two-hop neighbor of node \(N\). In which case, we have by assumption: \(Prio(Q)<Prio(N)\). * \(Q\) is a three-hop neighbor \(\in\mathcal{N}(N)\). In which case, we have by assumption: \(Prio(Q)<Prio(N)\). Hence, \(Maxprio3(N)=Prio(N)\). Hence, in both colorings, \(Prio(N)=max(Maxprio1(N),Maxprio2(N),Maxprio3(N))\). Conversely, let us assume:  
\(Prio(N)=max(Maxprio1(N),Maxprio2(N),Maxprio3(N))\). We now show than \(N\) can color itself. Since \(Prio(N)\geq MaxPrio1(N)\), no uncolored one-hop neighbor has a priority higher than \(N\). Since \(Prio(N)\geq MaxPrio2(N)\), no uncolored two-hop neighbor has a priority higher than \(N\), otherwise we would have the contradiction \(Prio(N)\geq MaxPrio2(N)>Prio(N)\). Since \(Prio(N)\geq MaxPrio3(N)\), no uncolored three-hop neighbor in \(\mathcal{N}(N)\) has a priority higher than \(N\), otherwise we would have the contradiction \(Prio(N)\geq MaxPrio3(N)>Prio(N)\). Hence, node \(N\) has the highest priority among the uncolored nodes in \(\mathcal{N}(N)\).