[mjpt777]

Can you point to a respected publication that states that is the definition of a wait-free algorithm, i.e. that other threads must help and it must cope with killing the thread externally?

By kill a thread I assume you mean use the OS to interrupt and terminate the thread from the outside while in such a simple algorithm and yet expect it to cope. Have you tried this on any java.util.concurrent classes and reported the "bugs" you have found? I'd be interested in the feedback you got. :-)

[danbruc]

This is the very definition of wait-free including the case that some concurrent operations never complete.

»A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes.« (Wait-Free Synchronization, Maurice Herlihy, 1991) [1]

As far as I can tell - I am definitely not an expert - there is no hard requirement that concurrent operations have to assist but it seems at least a common solution because undoing the partially completed work of other concurrent operations may have the consequence that they can not make progress and therefore the entire thing is no longer wait-free.

By the way, there is no requirement to explicitly kill the thread, you may as well just run out of stack space, the scheduler may decide to not assign a new time slice, cosmic rays may flip a bit in turn triggering a hardware exception because of an unknown instruction or just buggy or malicious code messing with the content of your address space. Every process can fail at any time.

[1] http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

[mjpt777]

Thanks for the link.

If you look at the implementation no thread is ever stopped from completing. If a producing thread was killed mid operation by another malicious thread then the stream is broken. Other threads are never blocked. Other writers can add via a finite number of steps and the stream will back pressure when flow control kicks in. The consumer is never blocked - it simply never sees more messages. The algorithm meets the definition.

Unless I missed it that paper does not not state that the algorithm must cope with a malicious thread to be wait-free.

Try applying your thinking to this other respected MPSC wait-free queue.

http://www.1024cores.net/home/lock-free-algorithms/queues/in...

[mjpt777]

I understand the point that we need to make software robust. No single algorithm can cope with every possible failure mode. That is why we need multiple instances run on multiple nodes to be resilient. This is independent from if this is a wait-free algorithm.