Making objects writable
Zahra Aghazadeh, Wojciech Golab, Philipp Woelfel · 2014
We devise a technique for augmenting shared objects in the standard n-process shared memory model with a linearizable Write{} operation, using bounded space and optimal worst-case step complexity. We provide a transformation of any shared object SW supporting only sequential Write{} operations into an object $W$ that supports concurrent Write{} operations. This transformation requires O(n2) SW objects and O(n2) O(log n)-bit registers, and each method (including Write{}) has, up to a constant additive term, the same time complexity as the corresponding method on object $SW$. Our implementation is deterministic, wait-free, and uses only shared registers (supporting atomic read and write operations). To the best of our knowledge, similarly efficient general constructions are not known even if stronger primitives such as CAS or LL/SC are available.