I don't think that is quite correct. By that definition, any alhorithm that is free of deadlocks would be a lock free algorithm. But, I'm fairly sure that isn't

I don't think that is quite correct. By that definition, any alhorithm that is free of deadlocks would be a lock free algorithm. But, I'm fairly sure that isn't the case - otherwise a hashmap protected by a single mutex would be considered a lock free data structure since as there is only a single mutex, deadlock would be impossible. I think the key paragraph from the Wikipedia article is: "In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)"