Abstract : Cloud applications are composed of a set of interconnected software components distributed over several virtual machines. There is a need for protocols that can dynamically reconfigure such distributed applications. In this paper, we present a novel protocol, which is able to resolve dependencies in these applications, by (dis)connecting and starting/stopping components in a specific order. These virtual machines interact through a publish-subscribe communication media and reconfig- ure themselves upon demand in a decentralised fashion. Designing such protocols is an error-prone task. Therefore, we decided to specify the protocol with the LNT value-passing process algebra and to verify it us- ing the model checking tools available in the CADP toolbox. As a result, the introduction of formal techniques and tools help to deeply revise the protocol, and these improvements have been taken into account in the corresponding Java implementation.