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.