International Journal of Computer
& Organization Trends

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.