# To reach k set consensus (k=2)

If I can use FIFO queue and read/write registers, can I reach wait free 2 set consensus if I have 3 processes? I thought is I can, but I saw a conclusion from text book says "we cannot achieve 2 set consensus on 3 processes in shared memory system", so I'm confused now.

Quoted from Chapter 16 of the book: Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2004):

(Page 345) We now show that there is no algorithm for solving $k$-set consensus in the presence of $f \ge k$ failures.

and

(Page 351) Theorem 16.7 There is no wait-free algorithm for solving $2$-set consensus problem in an asynchronous shared memory system with three processors.

The proof is quite complicated. See also the paper: The Asynchronous Computability Theorem for $t$-Resilient Tasks.

Yes you can. A FIFO queue has consensus number 2, thus you can implement 2-processors consensus using FIFO queues and registers. So, let processor 1 just decide its own input, and let processors 2 and 3 use 2-processors consensus to agree on one of their inputs and decide it. At most 2 values will be decided, thus solving 2-set-consensus among 3 processors.

Note that it is impossible to implement set-consensus using only shared memory (i.e. read-write registers). In distributed computing, a shared-memory system usually means a system in which only read-write registers are present, hence your textbook quote.