Common Contracts

Consensus and Set Agreement Algorithmss

May 2nd, 2020

• Filed
  May 2nd, 2020

Abstract. Process anonymity has been studied for a long time. Memory anonymity is more recent. In an anonymous memory system, there is no a pri- ori agreement among the processes on the names of the shared registers they access. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same register X, while the same name C may correspond to different shared registers for the processes p and q. This article focuses on solving the consensus and set agree- ment problems in the fully anonymous model, namely a model in which both the processes and the registers are anonymous. It is shown that consensus, and its weak version called set agreement, can be solved despite full anonymity, in the presence of any number of process crashes. As far as we know, this is the first time where non-trivial concurrency-related problems are solved in such a strong anonymity context. A noteworthy property of the proposed algorithms l