# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 4 The PingBasedDown Algorithm  
The PingBasedDown Algorithm is a distributed solution that helps to detect problematic nodes reliably, which therefore enhance the availability of decentralized clusters who use Gossip protocol as their main protocol to manage their membership. Each node in the cluster implements the full function of this algorithm.  
In our algorithm, we first collect enough data, which can be potentially used as network indicators \(I_{n}\), from application layer. After appropriately preprocessing, we bring them to the first model called Link Evaluation Model which is designed to estimate the link quality with the consideration of stochastic packet loss over TCP protocol. As for other message-based protocols such as UDP, the packet loss rate can be estimated simply using the ping-pong tests without this model so that we do not discuss them in this paper. The link evaluation results are then be used by the next model called Decision Model. It firstly evaluates the healthy status of the local and remote nodes and then determines the leadership. Finally, the node chosen as leader executes the faulty nodes selected by this model.  
Figure 2 shows the overall solution of the PingBasedDown algorithm.  
In preparation for describing in detail, we define some operators on the vector and set:  
Figure 2: Algorithm overview.  
**Definition 1**.: _(FindFirst: \(\mathbb{X}^{m}\times\mathbb{I}\rightarrow\mathbb{I}\)) Giving a vector \(X=(x_{1},x_{2},...,x_{m})\), \(FindFirst(X,\alpha)\) is defined as returning the subscript of the first value in \(X\) that equals to \(\alpha\). For example, suppose \(X=(1,3,5,5,4)\), \(FindFirst(X,5)=2\) because \(x_{2}\) is the first element in \(X\) that equals to \(5\)._  
**Definition 2**.: _(RemoveAt: \(\mathbb{X}^{m}\times\mathbb{I}\rightarrow\mathbb{X}^{m-1}\)) Giving a vector \(X=(x_{0},x_{1},x_{2},...,x_{m})\) and a subscript \(i,0\leqslant i\leqslant m\), \(RemoveAt(X,i)=(x_{0},x_{1},x_{2},...,x_{i-1},x_{i+1},...,x_{m})\). For example, suppose \(X=(1,3,5,5,4)\), \(RemoveAt(X,3)=(1,3,5,4)\)._  
Recall Section 3.3, to solve our problem we should first find a network indicator \(I_{n}(v_{i},v_{j})\), which is sensitive to packet loss and hence has the ability to estimate the quality of link.  
After the analysis of the collected data over TCP protocol with different packet loss rate, we find that the round-trip-time (RTT) of a TCP message is especially sensitive to stochastically packet loss. Here the RTT of a RPC message means time between a certain kind of message and its reply. We then fetch this feature and use it as the network indicator.  
To construct the input, i.e., \(I_{n}(v_{i},v_{j})\), of our model, the node \(v_{i}\) keeps collecting the most recent \(N_{w}\) groups of timestamps of communication records to \(v_{j}\). The timestamp group consists of the sending timestamp of a message and the receiving timestamp of its reply. We then calculate a RTT by subtract the two timestamps. Consider that it may take some time for a remote node \(v_{j}\) to process some of the messages, we should subtract the processing durations from corresponded RTTs. We denote \(T_{r}(v_{i},v_{j})\) to be the vector of collected RTT from \(v_{i}\) to \(v_{j}\), \(T_{p}\) to be a vector of processing delay corresponding to the vector of \(T_{r}\). Then, the notations of \(T_{r}\), \(T_{p}\) and the indicator \(I_{n}\) can be expressed as follows.  
\[T_{r}(v_{i},v_{j}),T_{p}(v_{i},v_{j}):V\times V\rightarrow\mathbb{R}_{+}^{N_{ w}},\]  
\[T_{r}(v_{i},v_{j})=\text{The most recently collected $N_{w}$ groups of round-trip-times},\]  
\[T_{p}(v_{i},v_{j})=\text{The processing time of messages corresponding to $T_{r}(v_{i},v_{j})$},\]  
\[I_{n}(v_{i},v_{j})=T_{r}(v_{i},v_{j})-T_{p}(v_{i},v_{j}).\]  
A simplified approach to construct the input is to collect the RTTs of messages which are supposed to be replied immediately, e.g., heartbeat messages. In this case, the indicator can be \(I_{n}(v_{i},v_{j})=T_{r}(v_{i},v_{j})\).