A deployment system orchestrates execution of deployment plan in coordination with nodes participating in deployment of a multi-tier application in a cloud infrastructure. The deployment system distributes local deployment plans to each node and maintains a centralized state of deployment time dependencies between tasks in different local deployment plans. Prior to execution of each task, deployment agents executing on each node communicates with the centralized deployment system to check whether any deployment time dependencies need to be resolved. Additionally, the deployment system utilizes a node task timer that triggers a heartbeat mechanism for monitoring failure of deployment agents.