So physically the operations for the subsequent writers completed after updating the length fields in their headers but logically they are not completed until they become visible to the reader and that requires updating the length field in the header of the failed writer. The situation seems even worse when the writer responsible to rotate the logs fails.
I did not look into the source code, they are probably dealing with failed writers, but the presentation alone does not provide any hints to me how they do it.
https://github.com/real-logic/Aeron/blob/master/aeron-client...
http://www.hermanmiller.com/products/seating/performance-wor...
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. :-)
»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.
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...
Try this. A process could have a rogue thread scribbling on memory and thus corrupting it. Such a process then that has this thread, by your definition, cannot be wait-free because any data structure can be corrupted and cause algorithms to fail. This is not how the concurrency community look at this.
*added below
Even a simple LOCK XADD instruction could have its results corrupted by this rogue thread after it writes before a consumer reads it.
And I obviously don't have to be an expert in the field to know that wait-free means that the algorithm must be able to handle processes making no progress because that is, as mentioned before, the definition.
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.
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?
In case of the SPSC queue the requirement is that the writer must be able to enqueue new items no matter what the reader does and the reader must be able to dequeue all items for which the enqueue operation succeeded no matter what the writer does afterwards. The presented queue implementation meets this requirements. If the writer fails between steps 4 and 5 the write did not succeed and it does not matter that the reader can not see the item.
What you say about keeping the data structure usable for other threads seems correct to me.
You must not confuse lock-free and not using a lock, these are two different things. An algorithm using locks is a blocking algorithm but using locks is only sufficient, not mandatory. If no process can block other processes unconditionally the algorithm is non-blocking and obstruction-free, lock-free and wait-free are different progress guarantees for non-blocking algorithms in ascending order of strength.
One last point, if you try to obtain a lock and fail to do so you are considered blocked, no matter if you spin, suspend the thread or do unrelated things to waste some time until retrying later.
However the data structure would be corrupt if writer one never completed. This is corruption and not the definition of wait-free.
You can even go a step further and make writer two block. Just assume that the next thing it does is waiting for a response from the receiver of its message. Now because writer one failed the message never reaches the receiver, the receiver never sends a response and the writer waits indefinitely for the response, i.e. is blocked. Now the failed writer one is really and the only reason writer two is blocked, even though only indirectly.
And you can not really call it a corruption of the data structure because it is the exact same stated that occurs during normal operation. If writer one would resume execution after two weeks suddenly the corruption would be gone.
Each thread under the algorithm can perform their actions in a finite number of steps without ever blocking. This means the producers can continue to do other work. The consumer can continue to consume from other log buffers without being blocked and complete in a finite number of steps. If a producer is killed mid operation then no further progress can be made on that log buffer. If this is considered blocking then the algorithm is blocking and therefore not wait-free. It would need to be killed by another malicious thread for this to happen.
What is clear is that this algorithm gives the best latency profile of of all the measured messaging systems and the highest throughput. I now have the challenge of searching for a name that best describes its behaviour.
And something I wanted to mention before but forgot to do - there is not only a problem if the responsible writer fails while trying to rotate the buffers but also if there is just another writer trying to write before the the buffer rotation completed. There is really not much you can do in this case besides retrying until you succeed. But this again also means that a writer may have bad luck and every time he looks a buffer rotation - not necessarily the same one - is in progress causing the writer to starve.
And just in case I wasn't clear about that, I am looking at all of this from a pretty theoretical point of view - I have at best a very rough idea what this will be used for in the real world and what scenarios are important and likely and what just doesn't matter. Actually maybe even the thing I just wrote is nonsense because nobody in your target audience will simply kill threads, but then again developers are notoriously good at bending and ignoring rules.