Systems and techniques are described for protecting virtual machines from network failures. A described technique includes running a virtual machine on a first source host; replicating, over a first network, data related to the virtual machine to a destination host; determining that the destination host has become unreachable, over the first network, from the first source host; determining whether a second source host can reach the destination host over the first network or a second network; determining whether the virtual machine can run on the second source host; and running the virtual machine on the second source host.