Primary and secondary virtual machines each executing on a separate physical host and forming a fault-tolerant pair synchronize their execution with each other as closely as possible such that the secondary can take over execution of the primary with little or no disruption of service and no loss of data. To provide fast takeover, the execution latency between the two virtual machines is kept to a minimum by incrementally adjusting the CPU allocation to the primary virtual machine. The CPU allocation to the primary virtual machine decreases when the execution latency is large and increases when the execution latency is small. In order to maximize the performance of the primary virtual machine, the system seeks to maximize the CPU resource limit for the primary virtual machine for as long as possible while minimizing the execution latency.