[yshalabi]

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.

[_benedict]

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.

[yshalabi]

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.

[tupshin]

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.