One of the fundamental problem in concurrency and synchronisation study is the wait-free construction of atomic registers. Atomicity simplifies programming by conjuring up an illusion of exclusive use of shared registers by concurrent processes; whereas wait-freedom improves the efficiency by guaranteeing that every process can proceed at its own speed, i.e. without being blocked by or needing to wait for other processes, even when they are accessing the same register simultaneously.

Much research work has been devoted to the study of the problem since Lamport and Peterson first posed it in the 70s. A plethora of ingenious algorithms has been discovered in the 80s and 90s, along with the invention of some of the classic techniques for concurrency and synchronisation, e.g. bounded timestamping techniques. Nowadays these algorithms and techniques become the foundation of scalable synchronisation research for modern multicore programming.

Despite the importance of the problem there is few substantial survey work done to summarise the field. Vitanyi published a very well-written note recently to retrace some of the history and recall some of the major results and steps to its solution [48]. Inspired by his work, we attempt in this report to give a more in-depth survey by 1) compiling a more comprehensive list of algorithms for atomic register construction, 2) organising and classifying the algorithms in a cube-like structure, and 3) providing a more accessible analysis on the classic techniques of bounded timestamping.