Introduction to Lock/Wait Free Algorithms: Defining and Understanding the Terms

The goal of this talk is to provide a working understanding of what it means for an algorithm to be lock/wait free. A brief recap of computer hardware design will motivate the need for concurrent algorithms. Without too much detail, the problems with typical synchronization primitives will be reviewed to introduce the desire for algorithms that do not use these primitives. Simple, working, easy-to-understand definitions for lock/wait freedom will be provided, and then compared and reconciled with common and exacting definitions. Use cases, implementation techniques, and common issues will be discussed with the intent of providing additional background information.