HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

The Committee Decision Problem

Abstract : We introduce the (b,n)-Committee Decision Problem (CD) - a generalization of the consensus problem. While set agreement generalizes consensus in terms of the number of decisions allowed, the CD problem generalizes consensus in the sense of considering many instances of consensus and requiring a processor to decide in at least one instance. In more detail, in the CD problem each one of a set of n processes has a (possibly distinct) value to propose to each one of a set of b consensus problems, which we call committees. Yet a process has to such that all processes deciding for the same committee decide the same value. We study the CD problem in the context of a wait-free distributed system and analyze it using a combination of distributed algorithmic and topological techniques, introducing a novel reduction technique. We use the reduction technique to obtain the following results. We show that the (2,3)-CD problem is equivalent to the musical benches problem of Gafni and Rajsbaum (DISC 2005), and both are equivalent to (2,3)-set agreement, closing an open question left there. Thus, all three problems are wait-free unsolvable in a read/write shared memory system, and they are all solvable if the system is enriched with objects capable of solving (2,3)-set agreement. While the previous proof of the impossibility of musical benches was based on the Borsuk-Ulam (BU) Theorem, it now relies on Sperner's Lemma, opening intriguing questions about the relation between BU and distributed computing tasks. // Ce rapport présente un problème de prise de décisionsmultiples (qui généralise le problème du consensus) et étudie sa calculabilité (à l'aide de techniques de réductions).
Document type :
Complete list of metadata

Contributor : Anne Jaigu Connect in order to contact the contributor
Submitted on : Friday, September 23, 2005 - 10:01:19 AM
Last modification on : Tuesday, June 15, 2021 - 4:14:48 PM
Long-term archiving on: : Thursday, April 1, 2010 - 9:01:19 PM


  • HAL Id : inria-00000290, version 1


Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers. The Committee Decision Problem. [Research Report] PI 1745, 2005, pp.17. ⟨inria-00000290⟩



Record views


Files downloads