We use a structured top-down approach to develop algorithms for atomic variables shared by concurrent asynchronous wait-free processes, starting from the problem specification. By this design we obtain a better understanding of what the algorithms do, why they do it, and that they correctly implement the specification. Our main construction of a multiwriter variable directly from 1-writer 1-reader variables is the first such construction. Simplifications yield multireader algorithms and multiwriter algorithms. The complexity improves that of known algorithms, in the cases where there were any. Our algorithms are timestamp based. We use a new “shooting” technique to recycle used timestamps.

dx.doi.org/10.1007/BFb0035779
European Conference on Numerical Mathematics and Advanced Applications
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

Li, M, & Vitányi, P.M.B. (1989). How to share concurrent asynchronous wait-free variables: Preliminary version. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 488–505). doi:10.1007/BFb0035779