Computer Science Department
Providence RI 02912
Instituto de Matemáticas
México City, D.F. 04510, México
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.