Set Consensus Using Arbitrary Objects

Set Consensus Using Arbitrary Objects

Maurice Herlihy
Computer Science Department
Brown University
Providence RI 02912
Sergio Rajsbaum
Instituto de Matemáticas
México City, D.F. 04510, México


In the k-set agreement 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, and the set of values chosen has 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 more powerful shared objects, such as test-and-set.

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)-set consensus, and the second addresses the question of what kinds of tasks can be solved by N processes using (M,j)-set consensus objects, for M \leq N.

Paper in Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Systems, August 1994, Los Angeles, pp. 324-333.

And Maurice Herlihy's slides.