[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...

[wflfof]

Regarding applying the wait/lock/obstruction freedom definition to Vyukov's MPSC implementation you reference.

It's clear that the MPSC design is not wait-free, nor is it lock-free. Dmitry identifies this fact in his initial postings about that design: https://groups.google.com/forum/#!topic/lock-free/Vd9xuHrLgg...

""" Push function is blocking wrt consumer. I.e. if producer blocked in (*), then consumer is blocked too. """

Between the XCHG and the update of next. If the producing thread completes the XCHG but fails to update next, all threads will fail to make progress. "Progress" in this case being the producers transferring data to the consumer. Put another way, in this algorithm a single misbehaving thread can prevent all threads from making progress.

Regarding the idea of "maliciousness", specifically if a participant thread is "killed mid-operation". That idea is the very definition of wait-freedom: that all participants complete the algorithm in a bounded number of their own steps, irrespective of the activities of other threads.

The definitions of wait/lock/obstruction freedom are well specified. I suggest the first half of _The Art of Multiprocessor Programming_ (the revised edition!) by Herlihy and Shavit for a deep dive.

[mjpt777]

I've read the _The Art of Multiprocessor Programming_ and am happy to read it again. Maybe I have misinterpreted.

So if "killed mid-operation" must be supported then I don't see how many algorithms can be said to make progress. Take for example the Lamport SPSC queue[1], if the producer gets killed mid operation between steps 4 and 5 of the push operation. Then the data is in the queue but the consumer is blocked from ever seeing it with this line of reasoning. The Lamport SPSC queue is considered wait-free by the concurrency community I know. I base my reasoning on this. What if the producer takes a pause for a long time between steps 4 and 5 before continuing?

However if to be wait-free an algorithm must allow all other threads to continue using the data structure, not just continue making progress in other ways by being non-blocking and completing in a finite number of steps, then I stand corrected.

If wait-free must include coping with any thread being killed mid operation is there a term for being lock-free but also having all threads not block and complete in a finite number of steps for their interaction with the algorithm?

[1] - http://arxiv.org/pdf/1012.1824.pdf

[danbruc]

Two threads want to send a single block message. Writer one advances the tail pointer by 100 bytes and then dies. Writer two then advances the tail pointer by another 100 bytes, copies its message into the buffer and writes its header. The reader will see the tail pointer 200 bytes past the last processed message but no valid header and this looks exactly like a writer currently in the process of placing a 200 byte message - including the header - into the buffer. Looks to me like thread one blocked thread two indefinitely because the message of thread two is never added to the buffer. Yes, the bytes are in the buffer, but only physically. The reader can not see them, i.e. the write operation did not logically complete.

[mjpt777]

If you look at the code the reader does not read the tail. It skips forward reading the length fields. It would never see the writer two message and it never blocks. It just thinks there are no new messages.

[saurik]

What if, instead of being killed, the thread runs arbitrarily slowly (at glacial speeds) between the two critical steps? Do other threads have to wait during that time, (Note: I haven't slept in days, not did I read the algorithm as my brain isn't working well enough to understand it, but I did seem to get the gist of this back/forth, and this seemed like an important detail.)

[mjpt777]

Please read the algorithm in code. No threads ever wait. :-)