The Space Complexity of Distributed Tasks in the Shared Memory Model

Abstract

In this thesis, I study the space complexity of the implementation of test-and-set and renaming problems from atomic multi-reader/multi-writer registers in distributed synchronous systems with n processes. Previously, Giakkoupis and Woelfel as well as Styer and Peterson showed that at least Omega(log n) registers are required to implement one-shot test-and-set objects. First, I show a deterministic obstruction-free test-and-set algorithm using O(sqrt n) unbounded registers. Next, I present a deterministic obstruction-free implementation of a one-shot test-and-set object from Theta(log n) registers of size Theta(log n) bits, which closes the gap between the upper and lower bound.

The problem of assigning unique names to processes from a set of size f(k) is called f-adaptive renaming, where k is the number of participating processes. Long-lived f-adaptive renaming allows each process to acquire and then release a name any number of times. One-shot adaptive renaming allows each process to get a name at most once. Let f: {1, ... ,n} -> N be a non-decreasing function satisfying f(1) <= n-1 and let d = max{x | f(x) <= n-1}. I show a lower bound of d + 1 registers for any non-deterministic solo-terminating long-lived f-adaptive renaming task. Furthermore, I observe that, this is a tight lower bound for long-lived (k+c)-adaptive renaming. However, for any non-deterministic solo-terminating one-shot (k+c)-adaptive renaming, I prove a lower bound of floor{2(n - c)/(c+2)} registers. I also provide two one-shot renaming algorithms: a wait-free one-shot (3k^2/2)-adaptive renaming algorithm from ceil{sqrt n} + 1 registers, and an obstruction-free one-shot f-adaptive renaming algorithm from min{n, x | f(x) >= 2n} + 1 registers.