A cloud availability manager configured to execute a recovery workflow that fails over one or more virtual machines (VMs) to and from a cloud computing system. In doing so, the cloud availability manager typically performs multiple operations for each VMs. The operations involve making several application programming interface (API) calls to component APIs of management components within the cloud computing system. To avoid bringing down the entire cloud infrastructure, the cloud availability manager throttles the API calls to other components while executing a recovery workflow. The throttling spans multiple instances (nodes) of the cloud availability manager and involves cooperation from the other management components to ensure the throttling is fair across all tenants of the cloud computing system.