Software updates within one or more regions of a multi-tenant cloud are coordinated. Tenant vs. tenant conflicts, tenant vs. infrastructure provider conflicts, and conflicts between security and another priority are identified and resolved using a shared update coordinator, update priority specifications, and availability specifications. An infrastructure update request may be presented to tenants for approval. Postponed infrastructure updates may be prioritized higher. Preventing exploits of zero-day vulnerabilities may be prioritized over meeting availability targets. Updates may be merged to reduce downtime, even when the updates originate from independently controlled entities. Maximum downtime, minimum fault domains, minimum virtual machines, permitted update start times, and other availability criteria may be specified. Updates may be preempted, or allowed to complete, based on their relative priorities. Tenants and infrastructure providers may still use their own deployment engines after updates are coordinated. Rogue behaviors involving adverse update approvals or disapprovals may be detected.