Set Consensus Using Arbitrary Objects

In the (N; k)-consensus task, each process in a group starts with a private input value, communicates with the others by applying operations to shared objects, and then halts after choosing a private output value. Each process is required to choose some process's input value, and the set of values chosen should have size at most k. This problem, first proposed by Chaudhuri in 1990, has been extensively studied using asynchronous read/write memory. In this paper, we investigate this problem in a more powerful asynchronous model in which processes may communicate through objects other than read/write memory, such as test&set variables. We prove two general theorems about the solvability of set consensus using objects other than read/write registers. The first theorem addresses the question of what kinds of shared objects are needed to solve (N; k)-consensus, and the second addresses the question of what kinds of tasks can be solved by N processes using (M; j)-consensus objects, for M N..