What is the exact consensus number of a multi-dequeuer queue?
I know that it is at least 2:
queue.enq(1)
queue.enq(0)
Thread A and B each call queue.deq().
The thread that got 1 will return it's own value.
The thread that got 0 will return the other's value.
But how do I prove it's exactly 2?
I think I should implement a queue using only 2-consensus objects, but I didn't manage to do it.
On
I think Adar Hefer's answer is correct. Still I kind of think, personal opinion, these formal answers are a pain.
As an informal answer. If you would have to get a consensus over multiple threads using a FIFO queue, how would you go about? So you can store three proposes, or more, no problem here. Than you can draw straws, either WIN, LOSE, or the second LOSE. Still no problem. But how do you get the correct 'voted upon' value? For a WIN you can just get your threadID, but how can you make sure both other threads also take the value of the winner? If you are a losing thread, from your standpoint you are unable to see which of the two other threads have won. All you know is that you've lost and should take an other proposed value. Gambling it away, you might draw the correct - you might not.
Assume that it can solve consensus for 3 threads. Consider a critical state in a tree of all possible linearized concurrent executions. Take a left, and you'll decide 1. A right, and you'll decide 0.
Assume thread A deq()'s from the queue, and then B deq()'s from the queue. Now we took the left branch. Assume then that thread B deq()'s from the queue and then A deq()'s from the queue. Now we took the right branch.
Now if thread C deq()'s from the queue, it shouldn't care which of the others deq()'d first. The queue will look identical to it either way.
A contradiction: Thread C will decide 2 different things even though the execution is identical as far as it's concerned.