M.Sc Thesis

M.Sc StudentPaz Ami
SubjectCounting-Based Impossibility Proofs for Distributed Tasks
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya
Full Thesis textFull thesis text - English Version


A cornerstone result in distributed computing is the impossibility of solving consensus using only read and write operations in asynchronous systems where processes may fail. The impossibility of solving consensus led to the study of sub-consensus coordination tasks, namely tasks that are weaker than consensus.

Two archetypal sub-consensus tasks are k-set agreement and M-renaming. In k-set agreement, n processes must decide on at most k of their input values; while n-set agreement is trivially solvable by each process deciding on its input, (n − 1)-set agreement is unsolvable. In M-renaming, processes decide on distinct names in a range of size M. When M is only a function of the total number of processes in the system, we call the task nonadaptive renaming, while if M is also a function of the number p of participants in the execution, we refer to the task as adaptive renaming. For any value of n, (2n − 1)-nonadaptive renaming is solvable, but surprisingly, (2n − 2)-nonadaptive renaming is not solvable if n is a prime power and solvable otherwise. For general values of n, the only previously known lower bound on the number of names necessary for nonadaptive renaming is n 1. For adaptive renaming, (2p − 1)-adaptive renaming is known to be solvable, while (2pp/(n−1))-adaptive renaming is not solvable.

Most previous impossibility proofs for (n−1)-set agreement, and all previous impossibility proofs for (2n − 2)-nonadaptive renaming, use nontrivial topological tools and notions in an innovative way. Nevertheless, the use of topological notions makes the interaction between the impossibility proofs and the operational arguments harder to understand, and makes the proofs less accessible to distributed computing researches.

We present simple proofs for the above mentioned impossibility results: n processes cannot solve (n − 1)-set agreement, and cannot solve (2pp/(n−1))-adaptive renaming; if n is a prime power, n processes cannot solve (2n − 2)-nonadaptive renaming. For general values of n, we give a lower bound for nonadaptive renaming, which is proved using a reduction between nonadaptive renaming for different numbers of processes, and using results about the distribution of prime numbers.

Our proofs consider a restricted set of executions, and combine simple operational properties of these executions with elementary counting arguments, to show the existence of an execution violating the task's requirements. This makes the proofs easier to understand, verify, and hopefully, extend.