Naming in Anonymous Distributed Systems
By Layla Aldawsari

Tuesday, April 13, 2021
9:00 am MT

Doctoral Thesis Committee:
Dr. Tom Altman, Advisor
Dr. Gita Alaghband, Committee Chair
Dr. Ashis Kumer Biswas, Committee Member
Dr. Liang He, Committee Member
Dr. Jahangir Karimi, Committee Member

ABSTRACT

Anonymous distributed systems consist of processes devoid of names that can identify them. The naming problem is to assign unique names to individual processes by a distributed algorithm. It is examined in two different communication models; shared-memory and beeping channels. For the shared-memory model, a system of anonymous processes is considered in both synchronous and asynchronous communication in several new models based on knowledge of the processes count and the available shared-memory. First, we considered shared-memory that consists of test-and-set (TAS) registers only. We developed two naming algorithms: the Sequential Lookup and the Random Lookup. Next, we considered shared-memory that comprises TAS and read/write registers. We developed three novel naming algorithms that are designed specifically for resource-constrained systems. The Counting, Global Counting, and Segment Shuffling algorithms are optimal in both shared memory size requirements and namespace size. Furthermore, we designed naming algorithms for new models where the processes communicate in multiple channels with beeps. Novel Las-Vegas and Monte-Carlo algorithms were developed for naming in both the strong and the weak models with optimal time complexities. The Multichannel Beep Naming and the Unknown Multichannel Beep Naming algorithms were designed for the strong model in which a process can only transmit a beep on a single channel. In the weak model, a process can transmit a beep on one or more channels and receive multiple beeps from more than one channel. The Multichannel Many Beep Naming and the Unknown Many Beep Naming algorithms were designed for such a model. The correctness of these naming algorithms has been formally proven in their designated models and their lower bound was analyzed. The proposed naming algorithms present a significant tool for the design of distributed algorithms in anonymous systems which can lead to solutions for other problems.