Concurrent structures, atomics and ABA

A linked list correct in one thread can fail under concurrent updates. One atomic instruction does not make a multi-step operation atomic. Linearizability requires each operation to appear instantaneous between invocation and response. Mutex designs need lock scope, ordering and exception-safe release.

Lock-free means system-wide progress; wait-free bounds each operation’s steps. Neither automatically means fast. CAS retries under contention. ABA changes an address A→B→A, hiding intervening changes from a simple comparison. Version tags, hazard pointers and epoch reclamation address related but distinct issues, including safe reuse.

Acquire/release and relaxed operations provide different visibility guarantees. The Python GIL is not a portable guarantee for every compound operation or runtime. C# Interlocked differs from Volatile. Tests need invariants and failure scheduling beyond stress runs. Production lock-free code requires a memory-model argument.

from threading import Lock,Thread
lock=Lock(); counter=0
def work():
    global counter
    for _ in range(1000):
        with lock: counter+=1
threads=[Thread(target=work) for _ in range(4)]
for t in threads:t.start()
for t in threads:t.join()
assert counter==4000