A computer-implemented method and distributed system for maintaining consistency of client applications on a plurality of server nodes may comprise providing a first and second versions of a distributed coordination engine (DConE). The first version of the DConE may receive proposals, reach agreements thereon and generate a first ordering of agreements that specifies an order in which the client applications are to execute the agreed-upon proposals and correspondingly update their respective states. A ChangeVersion proposal may then be processed by the first version of the DConE, whereupon the first version of the DConE may stop reaching any further agreements. A second version of the DConE may then take over reaching agreements on the proposals and generate a second ordering of agreements, beginning with the agreed-upon ChangeVersion proposal. Any agreed-upon proposal, received from the first version of the DConE after the agreed-upon ChangeVersion proposal, may be sent back to the second version of the DConE to enable the second version of the DConE to reach agreement thereon.