# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm
### Decision Model
#### 4.2.2 Leader Determination Module  
This module is to make healthy nodes find the cluster leader without election, i.e., find the function \(r_{c}\). Recall Table 1 (f), each node is given a unique id by function \(h(v)\). With the help of this function, the main idea of this module can be described as choosing the node from the healthy set with the minimal unique id to be the leader. Therefore, we define the basic candidate rule \(r_{c}\) to be:  
\[r_{c}(v_{i},v_{j})= \begin{cases}TRUE,&iff\;s^{\prime}_{n}(I_{v}(v_{j}))= Healthy,\\ FALSE,&otherwise.\end{cases}  \tag{18}\]  
However, in this case of the basic candidate rule, we can find that one \(v_{i}\) must obtain all remote nodes' healthy states, i.e., \(s^{\prime}_{n}(I_{v}(v_{j}))\) for all \(v_{j}\in V\setminus\{v_{i}\}\), which cannot be directly acquired locally. For this reason, an approach is needed to get or infer the status of remote nodes. Here we need to consider about the transitivity. Recall Section 3.2, this property is applicable in most cases but do have exceptions. Hence, we propose two different approaches classified by the applicability of this property. The first approach is to infer healthy states of remote nodes. In the most common conditions that transitivity is applicable, the two following theorems that can be proved:  
**Theorem 3**. : _When transitivity is applicable, for an arbitrary node \(v_{t}\), if it has a healthy link that connected to a healthy node \(v_{s}\), \(v_{t}\) must be healthy. This can be formulated as:_  
\[\forall v_{s},v_{t}\in V:\left\{ \begin{aligned} s_{n}(v_{s})= Healthy\\ s_{l}(v_{s},v_{t})=Healthy\end{aligned} \right\}\Rightarrow s_{n}(v_{t})= Healthy\]Proof. : Because \(s_{n}(v_{s})=Healthy\), according to Definition 4, we have:  
\[\exists V^{\prime}_{h}\ s.t.\left\{ \begin{aligned} &|V^{\prime}_{h}|>[\frac{|V|}{2}]-1,\\ &\text{nodes in $V^{\prime}_{h}$ are fully connected,}\\ & v_{s}\in V^{\prime}_{h}.\end{aligned} \right. \tag{19}\]  
Combine with (19), transitivity (2), and the fact that \(s_{l}(v_{s},v_{t})=Healthy\), it can be inferred that \(\forall v\in V^{\prime}_{h}\setminus\{v_{t}\},s_{l}(v,v_{t})=Healthy\). Thus, we have:  
\[deg(v_{t})>[\frac{|V|}{2}]-1 \tag{20}\]  
According to Theorem 1 and (20), the state of \(v_{t}\) can be demonstrated: \(s_{n}(v_{t})=Healthy\). **Lemma 3**. : _(With transitivity) For three nodes \(v_{i}\), \(v_{j}\) and \(v_{k}\), if the link state from \(v_{i}\) to \(v_{j}\) is Healthy and that from \(v_{i}\) to \(v_{k}\) is Unhealthy, it can be inferred that the link state from \(v_{j}\) to \(v_{k}\) is Unhealthy. This lemma can be formulated to:_  
\[\exists v_{i},v_{j},v_{k}\in V\ s.t.\ \left\{ \begin{aligned} & s_{l}(v_{i},v_{j})=Healthy\\ & s_{l}(v_{i},v_{k})=Unhealthy\end{aligned} \right\}\Rightarrow s _{l}(v_{j},v_{k})=Unhealthy\]  
**Theorem 4**. : _(With transitivity) For two nodes \(v_{s}\) and \(v_{t}\), if the state of \(v_{s}\) is Healthy, and the link between \(v_{s}\) and \(v_{t}\) is Unhealthy, it can be inferred that the state of \(v_{t}\) is Unhealthy._  
\[\exists v_{s},v_{t}\in V\ s.t.\ \left\{ \begin{aligned} & s_{n}(v_{s})=Healthy\\ & s_{l}(v_{s},v_{t})=Unhealthy\end{aligned} \right\}\Rightarrow s _{n}(v_{t})=Unhealthy\]  
Theorem 4 can be proved similar to the proof of Theorem 3. Proof. : According to Lemma 3 and (19), because the link status \(s_{l}(v_{s},v_{t})=Unhealthy\), we have inferred that \(\forall v\in V^{\prime}_{h}:s_{l}(v,v_{t})=Unhealthy\), which also can be expressed as \(deg(v_{t})<[\frac{|V|}{2}]\). Combine with Lemma 2, we can conclude that \(s_{n}(v_{t})=Unhealthy\). With Theorems 3 and 4, the state of a remote node can be easily inferred from the link evaluation results. In short, when the transitivity is applicable, if the state of a link starts with a healthy node is healthy, the destination remote node is in state of healthy. Hence the candidate rule \(r_{c}\) can be redefined to:  
\[r_{c}(v_{i},v_{j})= \begin{cases}TRUE,&iff\ s^{\prime}_{l}(I_{n}(v_{i},v_{j} ))=Healthy,\\ &FALSE,&otherwise.\end{cases}