Set Consensus Using Arbitrary Objects
Set Consensus Using Arbitrary Objects
Maurice Herlihy
Computer Science Department
Brown University
Providence RI 02912
herlihy@cs.brown.edu
|
Sergio Rajsbaum
Instituto de Matemáticas
U.N.A.M.
México City, D.F. 04510, México
rajsbaum@servidor.unam.mx
|
Abstract
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.