# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 3 Correctness Criteria for a Hybrid Checkpointing Model
### Checkpoint Indelibility Criteria  
In synchronous checkpointing strategy, the processes which joins the checkpointing can clear away the prior checkpoint when the checkpointing is finished. While the processes in asynchronous checkpointing strategy will eliminate checkpoints together after finding the global consistent checkpoint and finishing rollback recovery when some process fails, however, the checkpoints of one process not only include the \(\text{SC}_{\text{s}}\) related to MHs in same cluster, but also contain the \(\text{DC}_{\text{s}}\) related to MHs in different clusters in a hybrid checkpoint environment. When a process finishes the SC,  
In Figure 3, there are relations such as \(SC_{i,a,v}^{b}\Rightarrow DC_{i,k,s}^{m}\) and \(SC_{i,k,s}^{d}\Rightarrow\Rightarrow DC_{i,k,s}^{m}\). If \(P_{i,a,v}\) and \(P_{i,k,s}\) clear away \(SC_{i,a,v}^{b}\) or \(SC_{i,k,s}^{d}\) at once after finished \(SC_{i,a,v}^{b+1}\) or \(SC_{i,k,s}^{d+1}\), then \(P_{i,a,v}\) or \(P_{i,k,s}\) will not be able to roll back to global consistent states when \(P_{m,s,c}\) rolls back to \(SC_{m,s,c}^{t}\) (The correct rollback sequence is 1\(\rightarrow\)2\(\rightarrow\)3\(\rightarrow\)4).  
Let \(SC_{i}\) and \(SC_{k}\) be the \(SC_{s}\) of process \(P\). \(DC_{x}\) is the DC of \(P\) or the processes in the cluster same as \(P\). Then the indelibility criteria for checkpoint can be described as follows:  
**Criterion 5:** If \(\exists DC_{x}\) (\(SC_{j}\Rightarrow DC_{x}\) or \(SC_{j}\Rightarrow\Rightarrow DC_{x}\)) \(\land\)\(\exists SC_{k}\) (\(k\)\(\vartriangle\)\(i\)), then \(SC_{j}\) cannot be eliminated.  
Criterion 5 indicates that if one SC which is not newest depends on any DC directly or indirectly then it cannot be eliminated. Because the DC is an asynchronous checkpoint, it may cause a cascading rollback. As Figure 4 shows, the rollback of processes \(P_{m,s,c}\) and \(P_{m,j,t}\) will all cause \(P_{i,k,s}\) rolling back to \(DC_{i,k,s}^{m}\) (rollback 1 and 2 all cause the rollback 3). If \(DC_{i,k,s}^{m}\) is eliminated earlier than \(SC_{m,s,c}^{t}\) and \(SC_{m,j,t}^{y}\), then \(P_{i,k,s}\) will not be able to roll back to the consistent states with processes in \(C_{m}\) when \(P_{m,s,c}\) rolls back to \(SC_{m,s,c}^{t}\) or \(P_{m,j,t}\) rolls back to \(SC_{m,j,t}^{y}\).  
Therefore, the indelibility criteria of DCA can be defined as follows:  
**Criterion 6:** If \(\text{CKP}_{i}\) is not eliminated, then \(DC_{j}\) must not be cleaned up.  
Figure 4: Example of rollback in different clusters.  
Figure 3: Example of checkpoints dependence.  
Criterion 6 shows that if the checkpoints of \(\mathrm{MH_{s}}\) in different clusters which are dependent on one DC are not cleaned up, then this DC cannot be eliminated also. Otherwise, it will cause something wrong about rollback.  
**Criterion 7:** If \(\mathit{CRP_{i}}\) has been eliminated, then \(\mathit{DC_{j}}\) cannot be cleared away when one of the following conditions is satisfied.  
\(\mathit{DC_{j}}\) is the only checkpoint of \(\mathit{DP_{j}}\). \(\mathit{DC_{j}}\) does not depend on the checkpoints of \(\mathit{DP_{j}}\), but it depends on the checkpoints of processes in the same cluster of \(\mathit{DP_{j}}\).  
Th Criterion 7 means that if one DC is the only checkpoint of process or the DC is the earliest checkpoint and the \(\mathrm{SC_{s}}\) on which the DC depends are not eliminated, then the DC cannot be cleared away. The former requires that the new state of process be stored in an update checkpoint, while the later demands that the elimination of a DC will not cause wrong rollback. Hence, there will be one conclusion: if the hybrid checkpointing strategy satisfies the Criteria 1-7, then this strategy could assure the global consistency of checkpoints.