I'm not aware of any unsynchronized concurrent queue implementation. Being lock-free implies using Compare-And-Swap - a very powerful synchronization primitive.

I agree that the current implementation won't survive integer overflow, Java or not. That's fixable, though. Theoretically, algorithm's description would still use unbounded integers.

I disagree on atomic reads/writes. If the algorithm can deal with totally wrong values, why would partially wrong values make any difference? Atomic reads/writes certainly help with error probabilities but it's not clear to me to what extent. A C implementation will be as robust, Java doesn't add any magic here. A totally different CPU with no guarantee of atomic 4-byte updates would be needed. Do those exists?