Consider the following example as presented on stack overflow: 

http://stackoverflow.com/questions/30843279/stream-skip-behavior-with-unordered-terminal-operation

List<Integer> input = IntStream.rangeClosed(1, 20).collect(Collectors.toList());
Set<Integer> output = input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .collect(Collectors.toSet());

Skip should respect the encounter order of the list such that element "1" does not appear in the output set. However, this is not currently the case and the output set will be non-deterministic and contain one less element than the input list, where the input element not contained in the output set is essentially, for explanation purposes, selected at random.

The problem is the due to overly aggressive back propagation and application of the terminal characteristics to upstream operations. The terminal operation is unordered. This characteristic can be back propagated upstream for operations whereby they operate without respecting encounter order.

Back propagation currently stops at the first stateful short-circuiting operation (e.g. limit). This is incorrect as the skip operation should respect encounter order (if any) of the input stream. Further more, the distinct operation is also affected w.r.t. stability:

        List<Integer> input = IntStream.rangeClosed(1, 20).mapToObj(i -> new Integer(0)).
                collect(Collectors.toList());

        Integer v = input.get(0);
        System.out.println(Integer.toHexString(System.identityHashCode(v)));

        Collection<Integer> output = input.parallelStream()
                .distinct()
                .collect(Collectors.toSet());
        Integer v1 = output.iterator().next();
        System.out.println(Integer.toHexString(System.identityHashCode(v1)));


Back propagation was considered of primary benefit to elide a sort operation. Consider the following:

  stream.sorted(...).forEach(...)

Since the forEach terminal operation does not care about upstream encounter order the sort operation is essentially redundant.

However, the current back propagation implementation approach of flag manipulation cannot elide the sort operation. To support this would require a method on the stateful operation accepting the terminal flags and returning a boolean indicating whether propagation should continue or not. Then back-propagation would process the stateful operations in reverse order until the method returns false. In the interim of implementing such an approach (if so desired) the back propagation functionality should be removed.