http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency...
This might be relevant to answering your question.
http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency...
This might be relevant to answering your question.
Specifically does the every thread requirement rule out algorithms where there only one reader and one writer is allowed? If not, then this ring buffer is wait-free, since there is no CAS-and-retry step. (Of course an operation can fail because the queue is empty/full, but that is still completion).
* multiple/single producer, multiple/single consumer
* progress guarantees (wait-free, lock-free)
* bounded vs. unbounded
* whether it's double-ended or single-ended
* memory reclamation being dependant on a GC or not
* which atomic operations they need (e.g. some require double-CAS)
What you mention is a spsc bounded queue. this is about a mpmc unbounded queue. And from skimming the paper is seems like it does not require a GC either.
So it's far more powerful.
Of course spsc queues still have their use even if we have a good mpmc queue, they generally incur less overhead.