Counting-Based Impossibility Proofs for Renaming and Set Agreement
- Ami Paz, M.Sc. Thesis Seminar
- Monday, 9.7.2012, 14:30
- Taub 601
- Prof. Hagit Attiya
Perhaps the most celebrated results in distributed computing is the impossibility of solving consensus using only read and write operations in asynchronous system where processes may fail. One way to circumvent this result is to solve sub-consensus coordination tasks, which are weaker than consensus. Two archetypal sub-consensus tasks are k-set agreement and M-renaming, representing the classes of colorless and colored tasks, respectively. 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 his input, (n-1)-set agreement is unsolvable. In M-renaming, processes start with names from a large domain and must decide on distinct names in a range of size M. For any value of n, (2n-1)-renaming is solvable, but surprisingly, (2n-2)-renaming is impossible, if n is a prime power, while for other values of n, the only proved lower bound on the number of names is n+1. We present simple proofs for two impossibility results: n processes cannot solve (n-1)-set agreement, and, if n is a prime power, n processes cannot solve (2n-2)-renaming. We shall also discuss some properties of prime-powers, which are at the heart of the latter result. Both 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.