Research Article | Open Access | Download PDF
Volume 1 | Issue 2 | Year 2011 | Article Id. IJCOT-V1I2P304 | DOI : https://doi.org/10.14445/22492593/IJCOT-V1I2P304
A Non-blocking Checkpointing Algorithm for Non-Deterministic Mobile Ad hoc Networks
Kusum Saluja , Praveen Kumar
Citation :
Kusum Saluja , Praveen Kumar, "A Non-blocking Checkpointing Algorithm for Non-Deterministic Mobile Ad hoc Networks," International Journal of Computer & Organization Trends (IJCOT), vol. 1, no. 2, pp. 15-22, 2011. Crossref, https://doi.org/10.14445/22492593/ IJCOT-V1I2P304
Abstract
Mobile Ad-hoc Networks are a collection of two or more devices equipped with wireless communication and networking capability. These devices can communication with other nodes that immediately within their radio range or one that is outside their radio range. The transient failure probability of the computing process increases greatly with the enlarging of system scale. If a failure occurs in a process and there is not an appropriate method to protect it, more cost will be wasted for restarting the program. Coordinated checkpointing can be used to introduce fault tolerance in mobile ad-hoc wireless networks environment. In this paper we propose a new minimum process checkpointing scheme for ad-hoc networks. We assume that Cluster Based Routing Protocol (CBRP) is used which belongs to the class of Hierarchical Reactive Routing Protocols. The number of coordinated messages between a cluster head and its ordinary members is small. The recovery scheme has no domino effect and the failure process can rollback from its latest local consistent Checkpoint. We capture the transitive dependencies among processes by piggybacking dependency vector of the sending process along with the computation messages.
Keywords
Mobile Ad Hoc Network; Checkpointing; Fault tolerance; Coordinating Checkpointing.
References
[1] Cao G. and Singhal M., ―On the Impossibility of Min-process
Non-blocking Checkpointing and an Efficient Checkpointing
Algorithm for Mobile Computing Systems,‖ Proceedings of
International Conference on Parallel Processing, pp. 37-44,
August 1998.
[2] Cao G. and Singhal M., ―Mutable Checkpoints: A New
Checkpointing Approach for Mobile Computing systems,‖
IEEE Transaction On Parallel and Distributed Systems, vol.
12, no. 2, pp. 157-172, February 2001.
[3] Koo R. and Toueg S., ―Checkpointing and Roll-Back
Recovery for Distributed Systems,‖ IEEE Trans. on Software
Engineering, vol. 13, no. 1, pp. 23-31, January 1987.
[4] Parveen Kumar, Lalit Kumar, R K Chauhan, V K Gupta ―A
Non-Intrusive Minimum Process Synchronous Checkpointing
Protocol for Mobile Distributed Systems‖ Proceedings of
IEEE ICPWC-2005, pp 491-95, January 2005.
[5] Prakash R. and Singhal M., ―Low-Cost Checkpointing and
Failure Recovery in Mobile Computing Systems,‖ IEEE
Transaction On Parallel and Distributed Systems, vol. 7, no.
10, pp. 1035-1048, October1996.
[6] J.L. Kim, T. Park, ―An efficient Protocol for checkpointing
Recovery in Distributed Systems,‖ IEEE Trans. Parallel and
Distributed Systems, pp. 955-960, Aug. 1993.
[7] L. Kumar, M. Misra, R.C. Joshi, ―Low overhead optimal
checkpointing for mobile distributed systems‖ Proceedings.
19th IEEE International Conference on Data Engineering, pp
686 – 88, 2003.
[8] Murthy & Manoj, ―Ad hoc Wireless Networks Architectures
and Protocols‖, Pearson Education, 2004.
[9] D.J. Baker and A. Ephremides, ―The Architectural
Organisation of a Mobile Radio Network via a Distributed
algorithm‖, IEEE Trans. Commun., vol. 29, no. 11, pp 1694-
1701, Nov., 1981
[10] D.J. Baker, A. Ephremides and J.A. Flynn ―The design and
Simulation of a Mobile Radio Network with Distributed
Control‖, IEEE J. sel. Areas Commun.., pp 226-237, 1984
[11] B.Das, R. Sivakumar and V. Bharghavan, ―Routing in Ad-hoc
networks using a Spine‖,Proc. Sixth International Conference,
1997.
[12] B.Das, R. Sivakumar and V. Bharghavan, ―Routing in Ad-hoc
networks using Minimum connected Dominating Sets‖,Proc.
IEEE International Conference, 1997.
[13] M.Gerla, G. Pei, and S.J. Lee, ―Wireless Mobile Ad-hoc
Network Routing‖, Proc. IEEE/ACM FOCUS‘99, 1999.
[14] M. Singhal and N. Shivaratri, Advanced Concepts in
Operating Systems, New York, McGraw Hill, 1994.