A cluster of virtual servers includes a plurality of physical nodes, where each physical node executes virtualization software which implements a virtualization environment in which one or more virtual server machines execute. The virtualization software executed by each physical node may enable the virtualization environment implemented by the physical node to be dynamically changed. Some types of configuration changes to the virtualization environment may take a significant amount of time to perform, e.g., several seconds or longer. While the configuration change is taking place, the physical node may be unable to respond to messages sent by other physical nodes in the cluster of virtual servers. The nodes may execute message broadcast software which implements a message broadcast protocol which takes into account the dynamic configuration changes to the virtualization environments of the nodes in the cluster of virtual servers so that these periods of unresponsiveness can be handled gracefully.