Can Memory be used adaptively by Uniform Algorithms

Abstract. We introduce a novel term, memory-adaptive, that intuitively captures what it means for a distributed protocol to most efficiently make use of its shared memory. We also prove three results that relate to our memory-adaptive model. In our store/release protocols processors are required to store a value in shared MWMR memory so that it cannot be overwritten until it has been released by the processor. We show that there do not exist uniformly wait-free store/release protocols using only the basic operations read and write that are memory-adaptive to point contention. We further show that there exists a uniformly waitfree store/release protocol using only the basic operations read and write that is memory-adaptive to total contention. We finally show that there exists a uniformly wait-free store/release protocol using only the basic operations read, write, and write-plus that is memory-adaptive to interval contention and time-adaptive to total contention.