R.: Sharing is harder than agreeing

One of the most celebrated results of the theory of dis-tributed 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 abstrac-tions in a message passing system where a register is not a given physical device but is rather itself implemented by pro-cesses communicating through message passing. We show that, maybe surprisingly, the information about process fail-ures that is necessary and sufficient to implement a register shared by two particular processes is sufficient but not nec-essary to implement set agreement. We later generalize this result by considering k-set agree-ment, 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 ≤ k ≤ 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