# Data-Driven Packet Loss Estimation for Node Healthy Sensing in Decentralized Cluster
## 3 System Overview and Problem Formulation
### Problem Formulation  
The main weakness of gossip based membership management is that once a node receives a newer version of member state from a valid sender it will merge the state into its own state with only a simple conflict avoidance logic. This influences little on a normally working cluster. However, in some cases, a problematic but valid node gossiping corrupt member state can bring severe problem to the cluster. Stochastic packet loss is a typical case of a node being problematic but valid. In this case, the \begin{table}  
\end{table} 
Table 1: Formal system model. problematic node with unstable links to other nodes may mark a part of other nodes as Unreachable uncertainly if the failure detection mechanism is unreliable. Moreover, unlike network partition issue, this node still has possibility to gossip its globally incorrect member state. If the incorrect member state corrupts the cluster, it will cause at least 2 fatal problems:  
1. The leader may remove normal nodes that are marked as unreachable by the problematic one if the downing rule is not reliable. 2. There may be more than one nodes assume themselves to be leaders if all the normally working nodes with smaller unique id are marked by the problematic node. More specifically, a faulty node \(v_{f}\) marks a set \(V_{x}\subseteq V\setminus\{v_{f}\}\) of nodes as Unreachable by the process of \(\forall v\in V_{x}\) let \(fs(v_{f},v)\leftarrow\textit{Unreachable}\), and GossipTo \(v_{j},v_{j}\in V\setminus V_{x}\setminus\{v_{f}\}\). Finally, the member state might converge to a result that \(\forall v_{i},v_{j},v_{k}\in V\) s.t. \(fs(v_{i},v_{k})=fs(v_{j},v_{k})\). The commonly used original implantations of \(r_{c}\) and \(r_{d}\) are shown in Table 2. In this case, the uniqueness of leader cannot be guaranteed. As a result, it may happen that \(2\leqslant k\leqslant n\) (recall Table 1f, k stands for the quantity of leaders). Meanwhile, nodes in the set of \(V_{x}\) will be removed by these leaders after a period of time regardless of their actual node states. From the discussion above, we can draw 4 problems. First, an approach for estimating the severity of packet loss of link must be found. Second, faulty nodes must be prevented to make any decision on changing the size of cluster. Third, the uniqueness of leader node should be guaranteed. Finally, the leader need an approach to find faulty nodes and do responsible troubleshooting. These problems can be formulated as follows:  
(a) Link Estimate Problem (LEP)  
_Given:_ A local node \(v_{i}\) and a remote node \(v_{j}\). _Problem:_ Find a network indicator \(I_{n}(v_{i},v_{j})\) and a function \(s^{\prime}_{l}:I_{n}\to S_{n}\) such that the misrecognition rate of link state \(\sigma_{l}\) is minimized, which can be expressed as:  
\[\sigma_{l}(v_{i},v_{j},I_{n}):=P(s^{\prime}_{l}(I_{n})!=s_{l}(v_{i},v_{j})), \ \min\sigma_{l}.\]  
(b) Self Checking Problem (SCP)  
_Given:_ A local node \(v\). _Problem:_ Find a node indicator \(I_{v}(v)\) and a function \(s^{\prime}_{n}:I_{v}\to S_{n}\) such that the misrecognition rate of node state \(\sigma_{n}\) is minimized, which can be expressed as:  
\[\sigma_{n}(v,I_{v})=P(s^{\prime}_{n}(I_{v})!=s_{n}(v)),\ \min\sigma_{n}.\] \begin{table}
\begin{tabular}{|l|} \hline (a) The original implementation of function \(r_{c}\): \\ \(r_{c}(v_{i},v_{j})=\begin{cases}TRUE,&\text{iff }fs(v_{i},v_{j})=\textit{ Reachable}\\ FALSE,&\text{iff }fs(v_{i},v_{j})=\textit{Unreachable}\end{cases}\) \\ (b) The original implementation of function \(r_{d}\): \\ \(r_{d}(v_{i},v_{j})=\begin{cases}TRUE,&\text{iff }fs(v_{i},v_{j})=\textit{ Unreachable}\end{cases}\) for a period of time and do not recover \\ \(FALSE,&\text{otherwise}\) \\ \hline \end{tabular}
\end{table} 
Table 2: Original implementation of \(r_{c}\) and \(r_{d}\). (c) Leader Uniqueness Problem (LUP)  
_Given:_ The node set \(V\), the observation of connectivity from node \(v_{i}\) to \(v_{j}\) denoted by \(s^{\prime}_{l}(v_{i},v_{j})\).