Strata: wait-free synchronization with efficient memory reclamation by using chronological memory allocation

A locking is the typical mechanism to coordinate the race between multiple threads. But it downgrades the overall system performance due to the waiting time for the locked data to be unlocked. Wait-free synchronization is the one of the schemes to cope with the locking cost. The basic idea is making a replica of the shared data in order to manipulate it, and then applying the updated data. Due to the allocation of replicas without waiting, the most cost consuming step of wait-free synchronization is the reclamation of memory. This paper presents strata, a wait-free synchronization scheme with efficient memory reclamation. It allocates memory in the chronological order for efficient reclamation, and guarantees both update and read side wait-free in O(1) execution time.