Woelfel, PhilippHigham, LisaHelmi Khomeirani, Maryam2016-06-232016-06-2320162016Helmi Khomeirani, M. (2016). The Space Complexity of Distributed Tasks in the Shared Memory Model (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/28387http://hdl.handle.net/11023/3071In 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.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Computer Scienceasynchronous, shared memory modeldoctoral thesis10.11575/PRISM/28387