# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 6 Checkpointing and Recovery Algorithms
### Algorithm for Failure Recovery  
When a process fails, it firstly asks related processes to roll back to some global consistency states. Then these processes execute the operations stored in the logs. The keys of the correctness for rollback recovery are that determining the earliest rollback set of process and finding out the processes in different clusters belonging to the cascade rollback. **Definition 11**. : _The rollback set of \(P_{i}\) is the set of checkpoints to which the processes in same cluster and \(P_{i}\) may roll back, it is recorded as \(RS_{i}\)._  
**Definition 12**. : _The earliest rollback set is the set of earliest checkpoints to which the processes in same cluster and \(P_{i}\) must roll back, it is recorded as \(ERS_{i}\), \(ERS_{i}\subseteq RS_{i}\)._  
**Definition 13**. : _Let \(CKP_{i}\) to be the checkpoint to which the failure process \(P_{i}\) needs roll back. If \(\exists CKP_{k}(CKP_{k}\Rightarrow CKP_{i}\lor CKP_{k}\Rightarrow\)\(\Rightarrow\)\(CKP_{i})\), then \(CKP_{k}\in RS_{i}\)._  
**Definition 14**. : _Let \(P_{i}\) to be the failure process, \(P_{j}\) is the process in the cluster same as \(P_{i}\). \(CKP_{1}\), \(CKP_{2}\),..., \(CKP_{n}\) are the set of checkpoints of \(P_{i}\) and they belong to \(RS_{i}\). If \(\exists CKP_{x}\), \(x\in\{1,2,\,\ldots,\,n\}\), the condition \(CKP_{x}\)\(\Rightarrow\)\(CKP_{k}\) (\(k\in\{1,\,2,\,\ldots,\,n\}\), \(x\
eq k\)) is not satisfied, then \(CKP_{x}\in ERS_{i}\)._  
The ERS calculation procedure for failure process \(P_{i}\) is described as follows:  
1. \(P_{i}\) collects the \(IntraCDG_{s}\) of all processes in same cluster and builds the \(IntraCDGglobal\). 2. \(P_{i}\) executes the depth-first traversal to the \(IntraCDGglobal\) started from the checkpoint to which \(P_{i}\) has to roll back, and adds any checkpoints that can be arrived to the \(RS_{i}\). Finally, the earliest checkpoint of each process in \(RS_{i}\) is added to \(ERS_{i}\). Based on the \(ERS\), we define the following rollback rules:  
**Rule 4:** Let \(P_{i}\) to be the failure process. \(CKP_{x}\) is any checkpoint of process \(P_{j}\) in the cluster same as \(P_{i}\). If \(CKP_{x}\in ERS_{i}\), then \(P_{j}\) should roll back to \(CKP_{x}\). **Rule 5:** Let \(P_{i}\) to be the failure process. \(CKP_{x}\) is any checkpoint of process \(P_{j}\) in the cluster same as \(P_{i}\). \(CKP_{x}\in RS_{i}\). If \(\exists\text{Edge}(CKP_{x},DC_{x})\in S\_InterCDG_{m}\), then the related process in other cluster will be noticed to roll back to \(DC_{x}\). Let \(P_{i}\) to be the failure process and \(CKP_{i}\) to be the checkpoint to which \(P_{i}\) has to roll back. The rollback recovery algorithm is described as Algorithm 4. ```
\(P_{i}\)

**Proof. ** By contradiction. If the rollback strategy does not satisfy the correctness criteria, then there must be a message \(M\) there must be a message \(M\) whose sender process has cancelled the sending event of \(M\) but the receiver process does not cancel the receiving event of \(M\). Let \(P_{i}\) and \(P_{j}\) to be the sender process and receiver process of \(M\) respectively. \(CKP_{i}\) and \(CKP_{j}\) are the newest checkpoints of \(P_{i}\) and \(P_{j}\) when they send and receives \(M\), respectively. 1. \(M\) is a \(SM\). By the time \(P_{j}\) receives \(M\), the IntraCDG\({}_{\text{j}}\) of \(P_{j}\) will record the dependence relation of \(CKP_{j}\Rightarrow CKP_{i}\). If some process in the cluster same as \(P_{j}\) build the IntraCDGglobal for failure, then there must be a path from \(\text{CKP}_{\text{i}}\) to \(CKP_{j}\). Therefore, \(P_{j}\) is sure to roll back to \(CKP_{j}\) because \(CKP_{j}\) belongs to \(RS_{j}\) when \(P_{i}\) rolls back to \(CKP_{i}\) for failure or rollback request. 2. \(M\) is a DM. At present, \(CKP_{j}\) is \(DC_{j}\). After \(Pi\) sends \(M\), the cluster head \(CH_{k}\) of cluster same as \(P_{i}\) will firstly receive \(M\). When \(\text{CH}_{k}\) receives M, it transmits M and records the dependence relation of \(CKP_{j}\Rightarrow CKP_{i}\) in S_InterCDG\({}_{\text{K}}\).