1. An apparatus comprising: at least one processor; a memory coupled to the at least one processor; at least one streaming application residing in the memory and executed by the at least one processor, the at least one streaming application comprising a flow graph that includes a plurality of operators that process a plurality of data tuples; and a streams manager residing in the memory and executed by the at least one processor, wherein the streams manager monitors performance of the plurality of operators of the at least one streaming application and detects a failure that affects multiple consistent regions of the flow graph, and orders recovery of the multiple consistent regions based on dependencies of the multiple consistent regions.