# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 5 Strategies for Checkpoint Elimination
### Rules and Strategies of Checkpoint Elimination
#### 5.2.2 Elimination of \(DC\)  
It can be seen from Criterion 6, one \(DC\) must not be able to be cleared up if the related checkpoints of processes in other clusters on which the DC depends directly are not eliminated. Hence, one premise of DC to be cleaned up is that all checkpoints from other clusters on which the DC depends directly are cleared away. However, it needs to check whether the elimination of DC satisfies the conditions in Criterion 7 even if this premise meets. The elimination of \(\text{DC}_{\text{s}}\) is based on the elimination of \(\text{SC}_{\text{s}}\). If the conditions are satisfied, then the DC still cannot be cleared away. Let \(DC_{x}\) to be any DC of process \(P_{i}\). \(CKP_{i}\) is any kind of checkpoint of \(P_{i}\). \(CKP_{j}\) is any checkpoint of process in the cluster same as \(P_{i}\). Edge(\(A\), \(B\)) expresses the edge started by \(A\) and ended by \(B\) in \(IntraCDG\). Then the elimination rules of \(DC\) can be described in formalized way as follows:  
**Rule 2:** If \(\exists\)Edge (\(CKP_{i}\), \(DC_{x}\)) \(\in\)\(IntraCDG_{i}\), then \(DC_{x}\) can be cleaned up. **Rule 3:** If \(\exists\)Edge (\(CKP_{i}\), \(DC_{x}\)) \(\
otin\)\(IntraCDG_{i}\), then if only if \(\exists\)Edge(\(DC_{x}\), \(CKP_{i}\)) \(\in\)\(IntraCDG_{i}\)\(\wedge\)\(\exists\)Edge (\(CKP_{j}\), \(DC_{x}\)) \(\
otin\)\(IntraCDG_{i}\)), then \(DC_{x}\) can be cleaned up. Because the CH to which the sending process of DM belongs records \(S\_IntraCDG\), so the process needs to inform the CH to delete the checkpoint and related edges in \(S\_IntraCDG\) when the process cleans up the SC. If the CH finds the isolated DC \(DC_{x}\), then it informs the related cluster to judge whether the DC can be eliminated according to Rules 2 and 3. After receiving the processing request of the DC, the related process decides the next step operation by its own \(IntraCDG\). 1. If there is any edge which is started by checkpoint \(\mathit{CKP}_{i}\) of process and ended by \(\mathit{DC}_{x}\) in \(\mathit{IntraCDG}\), then \(\mathit{DC}_{x}\) will be cleared away. The edge which is started by and ended by \(\mathit{DC}_{x}\) will be eliminated. What is more, it will use \(\mathit{CKP}_{i}\) to replace \(\mathit{DC}_{x}\). Finally, the CH informs the processes in same cluster to change the \(\mathit{DC}_{x}\) to \(\mathit{CKP}_{i}\) in their own \(\mathit{IntraCDG}_{s}\). 2. If there is no edge started by the own checkpoint \(\mathit{CKP}_{i}\) of process and ended by \(\mathit{DC}_{x}\), and there is edge started by \(\mathit{DC}_{x}\) and ended by its own checkpoint \(\mathit{CKP}_{j}\), then two situations exist. 3. If there is not edge started by checkpoint \(\mathit{CKP}_{a}\) of process in same cluster and ended by \(\mathit{DC}_{x}\) in \(\mathit{IntraCDG}\), then can be cleared away. 4. If there is edge started by checkpoint \(\mathit{CKP}_{a}\) of process in same cluster and ended by \(\mathit{DC}_{x}\) in \(\mathit{IntraCDG}\), then turns \(\mathit{DC}_{x}\) to \(\mathit{SC}_{k}\) and informs other processes in same cluster to change \(\mathit{DC}_{x}\) in \(\mathit{IntraCDG}\) to \(\mathit{SC}_{k}\). **Theorem 1. **_The strategy of checkpoint elimination satisfies the correctness criteria of hybrid checkpointing model._  
**Proof. ** We prove this from the SC and DC, respectively:  
1. Let \(\mathit{SC}_{i}\) and \(\mathit{SC}_{j}\) to be the \(\mathit{SC}_{s}\) of any process \(P_{i}\). \(\mathit{DC}_{x}\) is any DC. According to Rule 1, if there is no path from \(\mathit{DC}_{x}\) to \(\mathit{SC}_{i}\) but there is node \(\mathit{SC}_{j}\) (\(j>i\)) in \(\mathit{IntraCDG}\)global, then it shows that \(\mathit{SC}_{i}\) is not the current checkpoint of \(P_{i}\) and there is no \(\mathit{DC}_{x}\) meeting the condition \(\mathit{SC}_{i}\Rightarrow\mathit{DC}_{x}\) or \(\mathit{SC}_{i}\Rightarrow\mathit{DC}_{x}\). At this moment, any rollback of process in different cluster will not cause \(P_{i,j,t}\) to roll back to \(\mathit{SC}_{i,j,t}^{y}\). Hence, \(\mathit{SC}_{i}\) can be eliminated.