# Design and Analysis of an Efficient Energy Algorithm in Wireless Social Sensor Networks
## 6 Checkpointing and Recovery Algorithms  
### Algorithm for Checkpoints in the Same Cluster  
Different from the traditional synchronous checkpointing strategy, when a process initializes the checkpointing, it firstly collects the dependence list of each process in the same cluster to obtain the dependence relation among processes. Then it finds out the processes that have to remain synchronous with it for realizing the checkpoints coordination of processes. However, if there are multiple processes initializing the checkpointing in the same cluster at the same time, then it will create unnecessary wireless communication overhead. Hence, let the CH of each cluster to control one token. In order to avoid the concurrent initializations, only the process which gets the token from CH is allowed to initialize the checkpointing. The all processes staying in active states in one cluster is named as the process list (PL). In order to reduce the occupation of useless checkpoints to the precious storage space of wireless terminals, this paper divides the \(\mathit{SC}_{s}\) into uncertain checkpoints and certain checkpoints (see the Definitions 2 and 3). If and only if the all processes which take part in the checkpointing finish the coordination of checkpoints, the uncertain checkpoints could be turned to certain checkpoints. Otherwise, these uncertain checkpoints will be eliminated, namely the caches released. Different from the DL which stores the list of processes depended on one process directly, the \(LDS\) stores the set of processes depended on one process directly and indirectly. The dependence relations in \(LDS\) can be achieved from _the \(DL_{s}\) of_ different processes:  
**Definition 8**. : _If \(P_{i}\) sends a message to \(P_{j}\), then \(P_{j}\) depends on \(P_{i}\) directly. It expresses as \(P_{j}{\rightarrow}P_{i}\)._  
**Definition 9**. : _If \(P_{k}{\rightarrow}P_{j}\) and \(P_{j}{\rightarrow}P_{i}\), then \(P_{k}\) depends on \(P_{i}\) transitively. It expresses as \(P_{k}{\rightarrow}P_{i}\)._  
**Definition 10**. : _The least dependence set (\(LDS\)) of \(P_{i}\) is the set of processes in cluster same as \(P_{i}\) which depends on \(P_{i}\) directly or transitively. If \(P_{j}{\rightarrow}P_{i}\) or \(P_{k}{\rightarrow}P_{i}\), then \(P_{j}\), \(P_{k}\in LDS_{i}\)._  
To describe the up-dependence relations, the dependence list (DL) is used to store the set of process which directly depends on one process, and so, the transitive dependence relation for \(LDS\) can be obtained from the \(DL_{s}\) of different processes. The steps of checkpointing in same cluster are described as follows:  
1. When process \(P\) receives \(K\), \(SM_{s}\), it sends token request to CH. If the token is not assigned, then \(P\) gets the token. Otherwise, \(P\) goes on applying for the token. During the interval, if \(P\) receives the checkpoint request from other process, then it takes an uncertain checkpoint. 2. After getting the token, \(P\) initializes the checkpointing. This procedure includes collecting the DLs of other processes, calculating \(LDS\) and so on. 3. \(P\) takes an uncertain checkpoint and sends checkpoint request and \(LDS\) to all of the other processes in same cluster. If some members stay in the disconnected states, it sends the information to the CH. 4. After getting the checkpoint request, the processes will take uncertain checkpoints if they are part of \(LDS\). Then they send replies to \(P\). 5. If \(P\) receives all of the positive replies, then it turns the uncertain checkpoint to certain checkpoint and notices the processes in \(LDS\) to turn. If some members stay in the disconnected states, \(P\) sends the turn request to the CH. If \(P\) does not receive all of the positive replies during a time interval, \(P\) clears away the uncertain checkpoint and informs all of the processes in the same cluster. 6.