Lock-freedom and wait-freedom are formal terms in concurrent algorithm theory. Best to check out Herlihy and Shavit, "The Art of Multiprocessor Programming," wh

Lock-freedom and wait-freedom are formal terms in concurrent algorithm theory. Best to check out Herlihy and Shavit, "The Art of Multiprocessor Programming," which I have unfortunately temporarily misplaced. Informally: "Lock-free" means that at each time step, at least one thread that is interacting with a shared object makes progress towards completing the operation (e.g. an enqueue or dequeue operation). Neither deadlock nor livelock (where no thread makes progress) can happen (hence "lock free"). This does not guarantee fairness or starvation-freedom (a fast thread could in-theory DoS a slow thread). "Wait-free" means that at each time step, every thread will make progress. This might e.g. involve an algorithm where fast threads help slow threads complete their operations. Wait-freedom is indeed a stronger condition, but it's usually more expensive to implement (although not always). > Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, lock-free algorithms make use of atomic instructions such as CAS (compare-and-swap). Sometimes it's used as a "commit" but there might be multiple atomic operations depending on the algorithm and the data structure (so I guess, a kind-of multi-phase commit sequence). This is a nice intro paper by one of the giants of the field: Maged M. Michael, "The Balancing Act of Choosing Nonblocking Features" ACM Queue vol. 11, no. 7 http://queue.acm.org/detail.cfm?id=2513575 http://queue.acm.org/detail.cfm?id=2513575 Update: I should add that "lock free" hasn't always been a formally defined technical term, and some people use it informally to mean "doesn't use mutexes," or even "only uses atomic operations." Under such a relaxed definition a hand-coded spin-lock might be considered "lock free," but it really isn't -- if a thread holding the spinlock crashes, the spinlock would never be unlocked; such a situation could not arise with a formally lock-free algorithm.