Fault Tolerance and Security vulnerabilities are related to each other in popularly growing mobile computing systems. Checkpoint-Recovery algorithms to provide fault tolerance has been designed here addressing mobility, handoff, resource limitations and security vulnerabilities of Mobile Cellular and Mobile Adhoc Network (MANET). Checkpointing algorithms using cryptography has been proposed to counter both active and passive attacks in Mobile Cellular network. To reduce encryption-decryption overheads in MANET, without having fixed infrastructure support, trust based checkpoint recovery has been proposed to ensure that only trusted nodes can participate in the process. Two trust models have been proposed, in one trust model nodes' trustworthiness are evaluated based on recommendation from other nodes, failure rate, availability or life time of a node in network,remaining battery power, and the other one is Ant Colony Optimization based trust model to ensure that checkpoints traverses through trusted mobile nodes only at recovery time. The algorithms are supported by theorems, lemmas, proofs, simulations wherever feasible.