Outside of social media (comment lists, facebook feeds, etc) are there any other examples where EC is an appropriate replacement of linearizability?
If you want sequential behavior from your datastructure in the presence of concurrency then, sorry, but linearizability is the only model that meets the requirements. I imagine 99% of programs want their concurrent lists/stacks/queues/maps to behave like their sequential counterparts.
I'm not sure if you read the article or not, but I try (and perhaps fail) to make clear that this is not so much eventual consistency in the distributed systems sense, since every accessor sees the same data (if not the same structure), but there are strong parallels with eventual consistency - in fact the same algorithm would work unchanged in an eventually consistent store, if it supported garbage collection. So I felt it helped to put readers in the right mindset.
Since only the structure is "eventually consistent" - the data that is represented by the structure is the same to every accessor, and is reliably (and efficiently) derived from all possible structural states, it behaves as much like its sequential counterpart as any other non-blocking data structure does.
Modern computer are eventually consistent systems by virtue of the caching layers (and local registers) - only once modifications make it to a shared cache are they globally visible. Much like with EC stores that support some kind of atomic read-modify-write operation, such an operation on a CPU incurs extra cost. However unlike in those systems, CPUs can read-modify-write non-transactionally very quickly, so the window for stepping on toes is low. In this structure, usually the desired outcome will be the actual outcome. So it can simply be cheaper to deal with the non-desired outcomes gracefully instead of ensuring they never occur.
Yeah, my question was more of a curiosity one regarding the utility of EC for applications. Sorry if it seemed like a brazen dismissal of your article. I am actually waiting to read your wait-free removal and lock-free append extensions.
Now I understand your first paragraph a bit better :P. I would avoid using EC. Instead I would find another term. To me, EC implies that the object can be inconsistent for some period of time but will eventually reach a consistent state across all nodes. Your titling of the link and your use of the EC term kind of threw me off a bit.
"Modern computer are eventually consistent systems by virtue of the caching layers (and local registers) - only once modifications make it to a shared cache are they globally visible."
I agree with you but I would leave registers/cache out of this. Yes, if a read to a memory location could return stale data then this would be absolutely be a problem. But I would argue that reading a memory location into a register then performing RMW ops on it does not necessarily put the system in an inconsistent state. This because RMW ops on a register dont change the actual shared object.
I think a better example for what you are talking about is write buffers in individual processor cores. These can contain intermediate state visible to that processor but not to others. Such relaxed consistency procesors will require appropriately placed fences to achieve linearizability.
The global banking system has always been eventually consistent (overnight reconciliation, etc). Eventual consistency is essential whenever communication latency exceeds the acceptable time to receive acknowledgement that an operation was performed.
The limiting factor used to be the speed of a horse, though now it is some approximation of the speed of light.
After a cursory read, I don't buy the guaranteed constant time claim.
"If there are so many competing adjacent deletes that you exceed this number of traversals, you just stop on the 10th deleted node and modify it, editing out the following 10 deleted nodes. The upshot is a list that steadily shrinks..."
...unless you're inserting and deleting more than 10 consecutive nodes all the time. Then the list steadily grows. Though I could be missing something.
1) The constant time claim for deletion is actually completely unrelated to the size of the list. Even if the list grew infinitely (only a fraction of all deletes were realised), the deletion would certainly be constant time since we explicitly bound it. Iteration would incur the cost, and reimpose the true structure as it went.
2) Regardless of the number of competing deletes, we always successfully remove some of the nodes we intended to - the question is only if an older delete in the same interval selected the same terminal node in one direction as a newer delete, and overrides the newer delete's pointer modification to reintroduce some nodes it had removed. Such an interleaving should be rare, especially as the range grows, since the newer delete both started later and had more work to do. The main risk is in situations where a thread is suspended in the middle of making its modification, in which case it could conceivably reintroduce a large range of previously removed nodes.
If you want sequential behavior from your datastructure in the presence of concurrency then, sorry, but linearizability is the only model that meets the requirements. I imagine 99% of programs want their concurrent lists/stacks/queues/maps to behave like their sequential counterparts.