# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm
### Decision Model
#### 4.2.2 Leader Determination Module
The \(\overline{\mathcal{R}_{k}}\) of AutoDown ranges from 8.9% to 48.1%, which indicates a poor performance on the accuracy of downning action. With our algorithm, the \(\overline{\mathcal{R}_{k}}\) in all test cases reach a perfect low rate 0.0%, which means that each removing action removes only faulty nodes. Therefore, we can conclude that the results prove the effectiveness and robustness of our proposed algorithm. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Size of Cluster** & **Faulty Nodes** & **Packet Loss Rate (\%)** & **Detection Rate \(\mathcal{R}_{D}\) (\%)** & **Mis-Kicking Rate \(\overline{\mathcal{R}_{k}}\) (\%)** \\ \hline
5 & 1 & 15 & 44.7 & 0 \\
5 & 1 & 25 & 58.3 & 0 \\
5 & 1 & 40 & 61.9 & 0 \\
5 & 1,3 & 15, 15 & 47.5 & 0 \\
5 & 1,3 & 25, 25 & 58.6 & 0 \\
5 & 1,3 & 40, 40 & 60.2 & 0 \\
5 & 1,3 & 15, 40 & 61.3 & 0 \\
5 & 1,3 & 25, 40 & 60.8 & 0 \\
5 & 1,3 & 15, 25 & 57.5 & 0 \\
7 & 1,2,3 & 15, 15, 15 & 54.4 & 0 \\
7 & 1,2,3 & 25, 25, 25 & 56.1 & 0 \\
7 & 1,2,3 & 40, 40, 40 & 66.4 & 0 \\
7 & 1,2,3 & 15, 40, 25 & 63.1 & 0 \\
7 & 1,2,3 & 40, 40, 15 & 67.2 & 0 \\
7 & 1,2,3 & 25, 25, 40 & 58.3 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: The system-level testing results. Each group is tested for 12 h.

## 6 Conclusions

In this work, we propose an algorithm that consists of Evaluation model and Decision model. This algorithm solves the problem of reduced availability in decentralized clusters when nodes occur to randomly drop packets. Driven by the application layer data, the Evaluation model estimates the link and gives relatively accurate evaluation on link quality. With the link evaluations, the Decision model further identifies the only leader. By modeling the cluster to a simple undirected connectivity graph, the leader finds a max clique of this graph. Then, the leader removes the nodes which are not in this clique in which way to make the cluster more stable and available. Classified by the applicability of transitivity, we simplified the NP-Complete maximum clique problem to a linear and a square complexity algorithm. We then evaluate our algorithm with statistical data. Moreover, we implement our solution and adopt it in a real-world product. All these results show that our approach is highly adaptable and available. [PERSON] designed the PingBasedDown algorithm, implemented the link evaluation model and decision model, collected and conducted analysis of the experimental data and did the comparative experiment. [PERSON] investigated the related work, implemented different kinds of failure detection algorithms as baseline methods and helped to formulate the system into the mathematical model. [PERSON] helped to provide the simulated production environment in Huawei Inc. and to polish the language and expression of the article. The authors declare no conflict of interest. ## References

* (1) Wikipedia. Computer Cluster--Wikipedia, The Free Encyclopedia. Available online: [[https://en.wikipedia.org/w/index.php?title=Computer_cluster&oldid=802238893](https://en.wikipedia.org/w/index.php?title=Computer_cluster&oldid=802238893)]([https://en.wikipedia.org/w/index.php?title=Computer_cluster&oldid=802238893](https://en.wikipedia.org/w/index.php?title=Computer_cluster&oldid=802238893)) (accessed on 20 October 2017). * (2) [PERSON]; [PERSON]. Decentralised approaches for network management. _ACM SIGCOMM Comput. Commun. Rev._**1997**, _27_, 36-47. * (3) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] A survey on fault-tolerance in distributed network systems. In Proceedings of the IEEE International Conference on Computational Science and Engineering (CSE'09), Vancouver, BC, Canada, 29-31 August 2009; Volume 2, pp. 1065-1070. * (4) [PERSON]; [PERSON] Fault tolerance mechanisms in distributed systems. _Int. J. Commun. Netw. Syst. Sci._**2015**, \(8\), 471-482. * (5) [PERSON]; [PERSON]; [PERSON] _A Gossip-Style Failure Detection Service_; Springer: London, UK, 1998; pp. 55-70. * (6) [PERSON]; [PERSON]; [PERSON] Implementation and Performance Evaluation of an Adaptable Failure Detector.