Techniques are disclosed for invalidating, at one or more processing elements, data streams containing data tuples. A plurality of tuples is received via a data stream, whereupon the data stream is determined to be invalid based on at least one tuple in the plurality of tuples. The data stream is then invalidated, and a message is issued that causes one or more data streams included in the stream-based computing system and related to the invalidated data stream to also be invalidated.