FULL PRODUCT VERSION : A DESCRIPTION OF THE PROBLEM : In the version of the tailSet method taking two arguments, in the implementation of java.util.Collections.SynchronizedNavigableSet, the method creates a new SynchronizedNavigableSet using the default mutex (this) rather than the correct mutex object for that set. This is the offending code: public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { synchronized (mutex) { return new SynchronizedNavigableSet<>(ns.tailSet(fromElement, inclusive)); } } Should be: public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { synchronized (mutex) { return new SynchronizedNavigableSet<>(ns.tailSet(fromElement, inclusive), mutex); } } REPRODUCIBILITY : This bug can be reproduced always.