# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm
### Decision Model
#### 4.2.2 Leader Determination Module
 \Rightarrow\left\{\begin{array}{c}(1)|S_{m}|\equiv 1,\\ (2)\\ &\exists K_{p}=\left(V_{m},\left( \begin{array}{c}V_{m}\\ 2\end{array} \right)\right),\\ & V_{m}=\left\{v_{x}:\left(v,v_{x}\right)\in E\right\}\cup\left\{v\right\} \text{ s.t. }K_{p}\in S_{m}.\end{split}\right.\end{split} \tag{25}\]

Proof: We let \(E_{m}=\left( \begin{array}{c}V_{m}\\ 2\end{array} \right)\), \(V_{R}=V\setminus V_{m}\). We also introduce the notations of \(K_{p}\), \(S_{m}\), \(V_{m}\), \(E_{m}\), \(G\), \(V\), \(E\) in Theorem 4.1 (25). _Maximal proof:_

Because the definition of \(V_{R}\) means a set of nodes with unhealthy link state with at least one node in set \(V_{m}\), which can be expressed as: \(\forall v\in V_{R}:\exists v_{h}\in V_{m}\text{ s.t. }(v_{h},v)\
ot\in E_{m}.\) We can then conclude that \(\forall v_{f}\in V_{R}:\); the graph \(\widetilde{G}=\left(V_{m}\cup\left\{v\right\},E_{m}\cup\left\{\left(v_{f},v_{h }\right):v_{h}\in V_{m},\left(v_{f},v_{h}\right)\in E\right\}\right)\) is not a complete graph, which means the graph \(K_{p}=\left(V_{m},E_{m}\right)\) is a maximal clique of the graph G.

_Maximum and unique proof:_

We assume that,

\[\exists K_{x}=\left(V_{x},\left( \begin{array}{c}V_{x}\\ 2\end{array} \right)\right),K_{x}\
eq K_{p},V_{x}\subset V\text{ s.t. }x\geqslant p,\text{ where }x=|V_{x}|. \tag{26}\]We denote \(V_{p}=V_{R}\cap V_{x}\), \(V_{q}=V_{m}\cap V_{x}\). If (26) is true, and because \(p>[\frac{|V|}{2}]-1\), we can infer that \(V_{p}\
eq\emptyset\), \(V_{q}\
eq\emptyset\). Then \(\exists v_{p},v_{q},v_{p}\in V_{R}\), \(v_{q}\in V_{m}\) s.t. \(v_{p}\in K_{x}\), \(v_{q}\in K_{p}\). Thus we have,

\[\exists v_{p},v_{q},v_{p}\in V_{R},v_{q}\in V_{m}\text{ s.t. }(v_{p},v_{q})\in E. \tag{27}\]

On the other hand, \(\forall v_{p}\in V_{R}\), \(\exists v_{q}\in V_{m}\) s.t. \((v_{p},v_{q})\
ot\in E\). According to Lemma 3, we have the inference that,

\[\forall v_{p}\in V_{R},\forall v_{q}\in V_{m},\,\exists(v_{p},v_{q})\text{ s.t. }(v_{p},v_{q})\in E. \tag{28}\]

(27) conflicts with (28), thereby the assumption (26) is false. Thus, \(\exists K_{x}\
eq K_{p}\) s.t. \(x\geqslant p\). Therefore, in this case, the leader node \(v_{l}\) can simply construct the global \(G^{\prime}\) from \(G^{\prime}(v_{l})\) and \(\overline{G}^{\prime}(v_{l})\) to approximate \(G\). With a loose policy that a leader will not remove a node with the link state of Pending between them, the \(G^{\prime}\) can be built with:

\[G^{\prime}=(V,E),E^{\prime}=\left( \begin{array}{c}V\\ 2\end{array} \right)\setminus\overline{E}^{\prime}(v_{l}). \tag{29}\]

Finally, with (24) and (29), we find the set \(V_{R}\):

\[V_{R}=\{v:(v_{l},v)\
ot\in E^{\prime}\} \tag{30}\]

The second scenario is that the transitivity is not applicable. In this case, we propose an easy-understanding, easy-implementing algorithm that will always find a maximal clique \(K_{p}\) of \(G\). Our idea is that, from the Self-Checking module, we can see that the healthy state of a node \(v_{x}\) has strong correlation with \(deg(v_{x})\). We therefore iteratively remove the node \(v_{f}\) with worst state, i.e., minimal \(deg(v_{f})\) until the rest of the nodes are fully connected. Algorithm 5 shows the process of this algorithm in details. ```
Input: global graph \(G=(V,E)\) Initialize: \(K_{p}=(V_{p},E_{p})\gets G\) \(V_{f}\leftarrow\emptyset\) while\(|E_{p}|<\frac{|V_{p}|(|V_{p}|-1)}{2}\)do \(R_{cand}\leftarrow\{v:v\in V_{p},deg_{K_{p}}(v)=\min_{v_{l}\in V_{p}}deg(v_{l})\}\) \(v_{f}\leftarrow\) a random \(v\in R_{cand}\) \(V_{p}\gets V_{p}\setminus\{v_{f}\}\) \(E_{p}\gets E_{p}\setminus\{(v,v_{f}):v\in V_{p}\setminus\{v_{f}\},(v,v_{f}) \in E_{p}\}\) \(V_{f}\gets V_{f}\cup\{v_{f}\}\) for\(v_{f}\in V_{f}\)do if\(\forall v_{h}\in V_{p}\) s.t. \((v_{f},v_{h})\in E\)then \(E_{p}\gets E_{p}\cup\{(v_{f},v):v\in V_{p}\}\) \(V_{p}\gets V_{p}\cup\{v_{f}\}\) if\(|V_{p}|<[\frac{|V|}{2}]\)then  Alert and prevent this leader execution. Output:\(K_{p}\)
```

**Algorithm 5**Finding a maximal clique. After the leader get the clique \(K_{p}=\left(V_{m},\left(