One of the key issues in the design of personal communication service (PCS) systems is the efficient management of location information. The current IS-41 and GSM schemes use a two-tier system of home location register (HLR) and visitor location register (VLR) databases. In a two-tier system, the success of a call requires the HLR and the callee’s current VLR to be failure-free. A VLR failure affects incoming calls to mobile hosts in the VLR’s location area. Meanwhile, if the HLR fails, it cannot direct calls to a mobile host from other hosts that are not in the same location area. Thus, tolerating the failures of the VLRs and HLR is important. In this paper, we propose a scheme, which tolerates the failures of the VLRs and HLR at the same time, without adding or changing any hardware of the systems. Moreover, our proposed scheme has lower HLR access rate, which can reduce the cost and delay in updating and querying. Experimental results show that our scheme can improve the performance of updating and querying in comparison with the traditional two-tier scheme. Therefore, our scheme is not only fault-tolerant but also cost effective.