Abstract: Due to the unreliable mobile hosts and the fragile network connection, it is significant to research on the fault tolerance of the mobile systems. Asynchronous rollback and recovery is suitable for the mobile hosts which move across cells and disconnect from the wireless networks from time to time. The existent rollback and recovery algorithms in the mobile computing environment can not completely implement consistent asynchronous recovery. A novel rollback recovery algorithm suitable to mobile environment based on causal message logging is presented. This algorithm takes advantage of antecedence graph to trace the message dependency of mobile hosts. Simultaneously, the storage of uncoordinated checkpoint, volatile sender-based message log and antecedence graph information is carried out on the mobile support station in order that the mobile hosts can gain a transparent fault tolerant service. This algorithm can tolerate multi-failures of mobile hosts when the mobile support station fails, and completely eliminate the effect of dependence among the mobile hosts. By means of formalization, the consistency of the system is proven. The simulation result shows that compared with the optimistic and pessimistic message logging, the causal message logging algorithm has the minimized rollback cost and communication, and storage cost in the failure free phase is enormously reduced.