Wait-Free Linearizable Implementation of a Distributed Shared Memory

Abstract: We consider wait-free linearizable implementations of shared objects which tol-erate crash faults of any number of processes on a distributed message-passing system. We consider the system where each process has a local clock that runs at the same speed as real-time clock and an message delays are in the range $[d-u, d] $ where $d $ and $u(0<u\leq d)$ are constants known to every process. We present four wait-free linearizable implementa-tions of $\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}/\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e} $ registers and two wait-free linearizable implementations of general ob-jects for several system settings. These are the first implementations with taking account of wait-freedom. Moreover, the worst-case response times of our wait-free implementations of $\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{d}/\mathrm{W}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e} $ registers on a reliable broadcast model is better than any previously known implementations