Sharing is Harder than Agreeing

One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of $n$ processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to decide on up to $n - 1$ among their n initial values. In short, the result indicates that the register abstraction is too weak to implement the set agreement one. This paper explores the relation between these abstractions in a message passing system where a register is not a given physical device but is rather itself implemented by processes communicating through message passing. We show that, maybe surprisingly, the information about process failures that is necessary and sufficient to implement a register shared by two particular processes is sufficient but not necessary to implement set agreement. We later generalize this result by considering k-set agreement, where the processes can decide on up to k values, and comparing it with a register shared by any particular subset of 2k processes. We prove that, for $1 \leq k \leq n/2$, (a) any failure information that is sufficient to implement a register shared by 2k processes is sufficient to implement $(n-k)$-set agreement but (b) a failure information that is sufficient for $(n - k)$-set agreement is not sufficient for a register shared by 2k processes. We also prove that (c) a failure information that is sufficient for a register shared by 2k processes is not sufficient for $((n-k)-1)$-set agreement.