FULL PRODUCT VERSION :
java version "1.8.0_144"
Java(TM) SE Runtime Environment (build 1.8.0_144-b01)
Java HotSpot(TM) 64-Bit Server VM (build 25.144-b01, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Darwin Kernel Version 17.0.0: Thu Aug 24 21:48:19 PDT 2017; root:xnu-4570.1.46~2/RELEASE_X86_64 x86_64

A DESCRIPTION OF THE PROBLEM :
While the API and internal documentation of ConcurrentLinkedDeque seem to indicate that single-element operations are linearizable, stress testing reveals otherwise.

I refer to the internal documentation as listed in code comments here:
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentLinkedDeque.java?revision=1.89

The internal documentation states: “we believe (without full proof) that all single-element deque operations (e.g., addFirst, peekLast, pollLast) are linearizable.”

Somewhat puzzlingly, the internal documentation continues with: “however, some combinations of operations are known not to be linearizable,” by which I suppose that “combinations” here refers to combinations of single-element deque operations with multi-element deque operations.

A very simple stress case demonstrates that single-element deque operations are not linearizable. In the following test, the addFirst(0) operation happens before the offer(1) operation, so if operations are indeed linearizable, then the poll() operation should never return 1; only 0 and null should be allowed. When run long enough, console output shows otherwise:

  nulls: 2450, zeros: 7, ones: 1

This can run for much longer though, depending on thread timings. For instance:

  nulls: 819440, zeros: 2176, ones: 1

This result seems to contradict the documentation.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the given test.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The test should not terminate.
ACTUAL -
The test terminates and prints a non-zero value of “ones”:

  nulls: 2450, zeros: 7, ones: 1

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeTest {
    static Integer value;

    public static void main(String[] args) {
        int nulls = 0, zeros = 0, ones = 0;

        while (ones == 0) {
            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();

            Thread t = new Thread() {
                public void run() {
                    value = d.poll();
                }
            };

            Thread u = new Thread() {
                public void run() {
                    d.addFirst(0);
                    d.offer(1);
                }
            };

            t.start();
            u.start();

            try { t.join(); } catch (Exception e) { }
            try { u.join(); } catch (Exception e) { }

            if (value == null) nulls++;
            else if (value == 0) zeros++;
            else if (value == 1) ones++;

            if ((nulls + zeros) % 10000 == 0)
                System.out.println("nulls: " + nulls + ", zeros: " + zeros + ", ones: " + ones);
        }

        System.out.println("nulls: " + nulls + ", zeros: " + zeros + ", ones: " + ones);
    }
}

---------- END SOURCE ----------