  Concurrent data structures often require additional memory for handling
synchronization issues in addition to memory for storing elements. Depending on
the amount of this additional memory, implementations can be more or less
memory-friendly. A memory-optimal implementation enjoys the minimal possible
memory overhead, which, in practice, reduces cache misses and unnecessary
memory reclamation.
  In this paper, we discuss the memory-optimality of non-blocking bounded
queues. Essentially, we investigate the possibility of constructing an
implementation that utilizes a pre-allocated array to store elements and
constant memory overhead, e.g., two positioning counters for enqueue(..) and
dequeue() operations. Such an implementation can be readily constructed when
the ABA problem is precluded, e.g., assuming that the hardware supports LL/SC
instructions or all inserted elements are distinct. However, in the general
case, we show that a memory-optimal non-blocking bounded queue incurs linear
overhead in the number of concurrent processes. These results not only provide
helpful intuition for concurrent algorithm developers but also open a new
research avenue on the memory-optimality phenomenon in concurrent data
structures.
