A streams manager intelligently restores multiple consistent regions of streaming applications in a streaming environment to increase performance and reduce overloading of other operators and resources. The streams manager detects a failure that affects multiple consistent regions and determines a preferred schedule to restore the multiple consistent regions by analyzing the relationships of the operators and resources associated with the multiple consistent regions. The streams manager may create a dependency graph that maps the interrelationships of the operators and resources associated with the consistent regions of the streaming application and then consult the dependency graph to determine the schedule to restore the multiple consistent regions affected by the failure.