An operator graph is established for processing elements configured to perform operations on tuples of streaming data. A first processing element in the operator graph includes a barrier operator that joins output of upstream operators. It is determined that at least one timeout condition has occurred at the barrier operator and substitute data tuple values are generated for missing tuple output data from at least one of the upstream operators. A first barrier tuple output is generated by joining the substitute data tuple values with received data tuple values from the upstream operators. A copy of the received data tuple values is stored. It is determined that a set of one or more tuples received at the barrier operator includes the missing tuple output data. A second barrier tuple output is generated by joining the missing tuple output data values with the copy of the received data tuple values.