Bachelor/Master Thesis
Analysing the renaming problem in shared memory
Text: Analysing the limits of distributed computability is an important topic in the era of blockchains. Although consensus protocols are employed in the real world, there is a frustrating theoretical result; as long as one process may crash, agreement cannot be reached in an asynchronous message passage model.
We will look at a similar problem — the renaming problem[1]. It was among the first non-trivial problems that were known to be solvable in a setting where consensus fails. In this thesis, we will analyse the renaming problem with the help of combinatorial topology. The application of combinatorial topology to distributed systems has an old and rich history. However, love for the abstract and mathematical rigour is a must for this thesis.
Objective: Understand and rephrase the theory (100% theory).