M.Sc Thesis | |

M.Sc Student | Paz Ami |
---|---|

Subject | Counting-Based Impossibility Proofs for Distributed Tasks |

Department | Department of Computer Science |

Supervisor | PROF. Hagit Attiya |

Full Thesis text |

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, (2*n* − 1)-nonadaptive renaming is solvable, but
surprisingly, (2*n* − 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, (2*p* −
1)-adaptive renaming is known to be solvable, while (2*p* − *p*/(*n*−1))-adaptive
renaming is not solvable.

Most previous impossibility proofs
for (*n*−1)-set agreement, and all previous impossibility proofs for
(2*n* − 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 (2*p* − *p*/(*n*−1))-adaptive
renaming; if *n* is a prime power, *n* processes cannot solve (2*n*
− 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.