# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm
### Decision Model
#### 4.2.2 Leader Determination Module
All the receivers then try to reply to \(v_{i}\) ReplyTopo messages containing their sub connectivity graphs and possibility containing the sub connectivity graphs of nodes cannot be reached by the sender. The function of \(\text{FetchAndCombine}\) will call the function Merge, which is presented in Algorithm 3, to merge different sub graphs after checking and resolving the conflict. Our default conflict resolving policy is that: if two sides give the detection result of an edge as a Pending and a non-Pending, the resolving result will be the non-Pending result; if two sides give the detection result of an edge as two different non-Pending results, the merging process will stop and give out the result of \"conflict\". For example, if \(v_{i}\) and \(v_{j}\) detects the edge \((v_{i},v_{j})\) to be \(Healthy\) and \(Pending\), respectively, after merging, the edge will be marked as \(Healthy\) which is to say the edge will appeared in the Healthy edge set \(E^{\prime}\); if \(v_{i}\) and \(v_{j}\) detects the edge \((v_{i},v_{j})\) to be \(Healthy\) and \(Unhealthy\), respectively, merging will be interrupted. Table 4 shows the detail of this policy. #### 4.2.3 Leader Execution Module

Leader node chosen by the former module uses leader execution module to find the set of \(V_{R}\) and removes these nodes in \(V_{R}\) from the cluster. Then, for a leader node \(v_{l}\) and an arbitrary remote node \(v_{x}\), the downing rule can be described as follows:

\[r_{d}(v_{l},v_{x})= \begin{cases}TRUE,&\text{iff }v_{x}\in V_{R},\\ FALSE,&\text{otherwise}.\end{cases}  \tag{23}\] \begin{table}
\begin{tabular}{c c c} \hline \hline
**Edge State 1** & **Edge State 2** & **Merge Result** \\ \hline \(Healthy\) & \(Healthy\) & \(Healthy\) \\ \(Unhealthy\) & \(Unhealthy\) & \(Unhealthy\) \\ \(Healthy\) & \(Pending\) & \(Healthy\) \\ \(Unhealthy\) & \(Pending\) & \(Unhealthy\) \\ \(Pending\) & \(Pending\) & \(Pending\) \\ \(Healthy\) & \(Unhealthy\) & Conflict \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Edge merging policy. We construct \(V_{R}\) based on the idea that after the execution, the rest of the nodes can normally transmit data with each other, which is to say they form a complete graph from the perspective of graph theory. So we abstract the objective of this module to be (1) find a maximal clique, with best effort, a maximum clique, of \(G^{\prime}\), which means finding a subgraph \(K^{\prime}_{p}=\left(V_{m},\left( \begin{array}{c}V_{m}\\ 2\end{array} \right)\right)\) of \(G^{\prime}\) with maximal or maximum nodes satisfying the condition that \(K^{\prime}_{p}\) is a complete graph; (2) let \(V_{R}:=V\setminus V_{m}\). The MCP (max clique problem) is a NP-Complete problem [24]. Therefore, we need an algorithm to reduce the computing complexity to make our algorithm available in big clusters. In this section, according to the applicability of transitivity, we propose two algorithms for each case. In the first case with the property, our algorithm will always find a max clique with the computing complexity of \(\mathcal{O}(|V|)\). While in the second case without the property, we propose simple heuristic algorithm that will find a maximal (maybe max) clique with the computing complexity of \(\mathcal{O}(|V|^{2})\). The first scenario is that the transitivity is applicable. In this case, the leader \(v_{l}\) can find a max clique by a very simple policy of:

\[ \begin{split}&\text{let }V_{m}\leftarrow\left\{v:v\in V\setminus \left\{v_{l}\right\},\left(v_{l},v\right)\in E\right\}\cup\left\{v_{l}\right\},\\ & K_{p}=\left(V_{m},\left(\begin{array}{c}V_{m}\\ 2\end{array}\right)\right),\text{where }p=|V_{m}|.\end{split}  \tag{24}\]

This is because the theorem below can be proved. Theorem 4.1: _With the transitivity, a healthy node and all its peers end with healthy links construct the unique max clique of the global graph \(G\)._

\[ \begin{split}& G=\left(V,E\right)\text{ is an undirected graph.}\\ & S_{m}\text{ is a set of max cliques of }G.\\ &\exists v\text{ s.t. }deg_{G}(v)>[\frac{|V|}{2}]-1\end{split}