Many distributed applications deployed on the Internet must operate continuously with no noticeable interruption of service. Such 24/7 availability requirements make the maintenance of these application difficult because fixing bugs or adding new functionality necessitates the online replacement of the software version by the new one, i.e., a “live update”. Support for “live update” is therefore essential to allow software evolution of critical services. While the problem of live update has been widely studied and several techniques have been proposed (e.g., using group communication and replication), we propose in this paper an original approach for the dataflow-based programming model (FBP). An interesting property of FBP is its seamless support for multiand many-core architectures, which have become the norm in recent generation of servers and Cloud infrastructures. We introduce a framework and new algorithms for implementing coordinated non-blocking updates, which do not only support the replacement of individual software components, but also modifications of structural aspects of the applications independently of the underlying execution infrastructure. These algorithms allow us to transparently orchestrate live updates without halting the executing program. We illustrate and evaluate our approach on a web server application. We present experimental evidence that our live update algorithms are scalable and have negligible impact on availability and performance.