This issue seems to be reproducible with 8-lambda builds only, not the main promotions.

Consider the following code:

        PriorityQueue priorityQueue = new PriorityQueue<>(Arrays.asList("a", "b", "c"));
        Stream stream = priorityQueue.stream();
        Stream parallel = (Stream)stream.distinct().parallel();
        Iterator iterator = parallel.iterator();

        System.out.println("next = " + iterator.next());
        System.out.println("next = " + iterator.next());
        System.out.println("next = " + iterator.next());


The order of the elements in the output will be random with 8-lambda but will remain sorted with 8-main promotions.

The following JCK test will fail due to this issue:

api/java_util/PriorityQueue/Stream.html#Stream[checkDistinct]
api/java_util/PriorityQueue/ParallelStream.html#ParallelStream[checkDistinct]