Resources in an Infrastructure-as-a-Service (IaaS) system are upgraded in an iterative process. In response to an upgrade request indicating requested changes to a current configuration of the system, one or more graph representations of the current configuration and the requested changes are created. The graph representations include a control graph which has vertices representing resource groups, and edges representing dependences among the resource groups. A batch of resource groups is identified to be upgraded in a current iteration based on the dependencies and Service Level Agreement (SLA) requirements including availability and elasticity of the system. Upgrade operations are executed on the identified batch using selected upgrade methods which handle potential incompatibilties during transition of system configurations. The graph representations are updated to include any new requested changes and recovery operations in response to feedback of failed upgrade operations. The iterative process proceed to upgrade remaining one or more resource groups.