Large-scale overlays has become a powerful paradigm for deploying stream processing applications in wide- area environments. The dynamic nature of these systems makes it difficult to guarantee the Quality of Service (QoS) requirements of each application. In this work we present a framework for distributing stream processing applications, where processing components and stream flows could be shared across multiple applications. In our approach, nodes coordinate to precompute alternative network deployments for each application that respect both node constraints and the applications' QoS requirements. Given this set of alternative deployments, nodes can react fast to changes on the network conditions, workload or application expectation.