# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm
### Decision Model  
With the link evaluation results, the decision model is proposed to solve the following three problems, first is whether a node itself is healthy(SCP), second is whether a node is the leader who is responsible for removing faulty nodes(LUP), third is which nodes are faulty(FNDP). We denote the cluster (nodes and its links) to be a simple undirected graph \(G=(V,E)\), where \(E=\{(v_{i},v_{j}):\forall v_{i},v_{j}\in V,s_{l}(v_{i},v_{j})=Healthy\}\). As shown in Figure 3, with the help of evaluation model, a node \(v_{i}\) can build a group of subgraphs \(G^{\prime}(v_{i})=(V,E^{\prime}(v_{i}))\) and \(\overline{G}^{\prime}(v_{i})=(V,\overline{E}^{\prime}(v_{i}))\) with the result of Evaluation model. Similar to the relationship between \(s_{l}\) and \(s^{\prime}_{l}\), \(E^{\prime}\) (and also \(\overline{E}^{\prime}\)) is the observation of \(E\). If an edge is in the set \(E^{\prime}\), the evaluation result of this link is Healthy. As for edges existing in \(\overline{E}^{\prime}\), their evaluation results are Unhealthy. If an edge \((v_{i},v_{j})\) is neither in \(E^{\prime}(v_{i})\) nor in \(\overline{E}^{\prime}(v_{i})\), its evaluation result is Pending. Formally, \(E^{\prime}\) and \(\overline{E}^{\prime}\) are defined as follows:  
\[E^{\prime}(v_{i}) :=\{(v_{i},v):\forall v\in V,s^{\prime}_{l}(I_{n}(v_{i},v))=Healthy\}, \tag{8}\] \[\overline{E}^{\prime}(v_{i}) :=\{(v_{i},v):\forall v\in V,s^{\prime}_{l}(I_{n}(v_{i},v))=Unhealthy\}. \tag{9}\]  
Next, we present some definitions about the node state. **Definition 3**. : _Healthy node set. \(W\) is the healthy node set if and only if the following 3 conditions are satisfied: (1) \(\forall v_{1},v_{2}\in W\), \((v_{1},v_{2})\in E\); (2) \(|W|\geqslant\lfloor\frac{V}{2}\rfloor\); (3) \(\
ot\exists v\in V\) s.t. \(\forall v_{h}\in W,(v,v_{h})\in E\)._  
**Definition 4**. : _Healthy node. A node \(v\) is Healthy if and only if \(v\in W\)._  
**Lemma 1**. : _When a cluster is normally working, if a node \(v_{i}\) is healthy, the degree of \(v_{i}\) in \(G\) must be greater than \(\lfloor\frac{|V|}{2}\rfloor-1\)._  
\[(1),s_{n}(v_{i})=Healthy\Rightarrow deg(v_{i})>\left\lceil\frac{|V|}{2}\right\rceil-1 \tag{10}\]  
Proof. : Let \(V_{h}:=\{v:v\in V,s_{n}(v)=Healthy\}\), \(V^{\prime}_{h}:=V_{h}\setminus\{v_{i}\}\). Because of (1), we have \(|V_{h}|>\left\lceil\frac{|V|}{2}\right\rceil\), and according to the definition of \(V^{\prime}_{h}\), we have:  
\[|V^{\prime}_{h}|>\left\lceil\frac{|V|}{2}\right\rceil-1 \tag{11}\]  
With Definition 4, we have \(deg(v_{i})=|V^{\prime}_{h}|-1\). Combining with (11), we have \(deg(v_{i})>\left\lceil\frac{|V|}{2}\right\rceil-1\)  
**Lemma 2**. : _A node \(v_{i}\) is unhealthy, if and only if the degree of \(v_{i}\) in \(G\) must lower than \([\frac{|V|}{2}]\)._  
\[(1),s_{n}(v_{i})=Unhealthy\Leftrightarrow deg(v_{i})<[\frac{|V|}{2}] \tag{12}\]  
From Lemma 1 we see that the condition that \(deg(v_{i})>[\frac{|V|}{2}]-1\) is only the necessary but not the sufficient condition of that \(v_{i}\) is healthy. However, these nodes with degree greater than half of the cluster size are also potentially healthy, which may need further determination. Thus, we make a new definition with this kind of nodes to be PendingHealthy. **Definition 5**. : _If the degree of a node \(v\) in \(G\) is greater than \([\frac{|V|}{2}]-1\), we say that it is PendingHealthy._  
\[deg(v_{i})>[\frac{|V|}{2}]-1\Leftrightarrow v_{i}\;\text{is PendingHealthy} \tag{13}\]  
Particularly, when the transitivity is applicable, if a node is PendingHealthy, it must be Healthy. **Theorem 1**. : _When the transitivity is applicable, if a node is PendingHealthy, it is Healthy. This can be expressed as:_  
\[(1),(2),deg(v_{i})>[\frac{|V|}{2}]-1\Rightarrow s_{n}(v_{i})=Healthy \tag{14}\]  
Proof. : We let \(V^{\prime}_{h}:=\{v:v\in V,s_{l}(v_{i},v)=Healthy\}\cup\{v_{i}\}\).