|Title:||Counting-Based Impossibility Proofs for Distributed Tasks
|Abstract:||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 (2p − p/(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 (2p − p/(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.
|Copyright||The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information|
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2013/MSC/MSC-2013-11), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.
To the list of the MSC technical reports of 2013
To the main CS technical reports page
Computer science department, Technion