One major breakthrough on the communication society recently is the extension of networking from wired to wireless networks. This has made possible creating a mobile distributed computing environment and has brought us several new challenges in distributed protocol design. Obviously, wireless networks do have some fundamental differences from wired networks that need to be paid special attention of, such as lower communication bandwidth compared to wired networks, limited electrical power due to battery capacity, and mobility of processes. These new issues make traditional recovery algorithm unsuitable. In order to cope with these problems, the tasks of logging and recovery procedure are performed by the MSSs. In this paper, we propose an efficient algorithm with O(n/sub r/) message complexity where O(n/sub r/) is the total number of mobile hosts (MHs) related to the failed MH. In addition, these MHs only need to rollback once and can immediately resume its operation without waiting for any coordination message from other MHs. During normal operation, the application message needs O(1) additional information when it transmitted between MHs and mobile support stations (MSSs). Each MSS must keep an n/sub total-h/*n/sub cell-h/ dependency matrix, where O(n/sub total-h/) is the total number of MHs in the system and n,,n h is the total number of MHs in its cell.