Implementing wait-free consensus with queues

Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the first process to dequeue it "wins".

However, it is also possible to do wait-free consensus with queues that start off empty (for example, given as an assignment here, question 1).

I wasn't able to come up with the algorithm - would like help.

A hand-wave explanation: Two processors run asynchronously and communicate via shared memory, with atomic reads and writes being basic operations. We want to solve the wait free consensus problem, where each process starts with a bit value and they need to agree on one of the values, in a way that is wait free: each processor can finish in a finite number of its own steps, regardless of the progress of the others. A result says that such a task can't be done, so we include objects with more powerful operations that will allow consensus. The consensus number of an object is the number of processors in the model that can reach consensus using it. The consensus number of a queue with just enq and deq is 2. Intuitively it isn't 3 because if a processor deqs empty, it can't know which of the other processors deqd the value.

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question.

We study how initialization of shared objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus
between two processes, we prove that an initially empty queue or stack cannot.

However, with a tiny extra resource such as a 1-bit safe register, an empty queue or stack suffices to solve consensus.

Please check Section 5 for impossibility proof and algorithm.

Please also check the paper "On the Importance of Registers for Computability" by Rati Gelashvili, Mohsen Ghaffari, Jerry Li, and Nir Shavit, 2014.

In the second paragraph of Introduction, the authors claim that:

(1) We show that $\ldots$ two queues in arbitrary initial states are sufficient for solving two process consensus.

(2) On the other hand, we prove that it is impossible to solve two process consensus using a single empty queue.

A little conclusion is:

In other words, unless you have multiple queues or multiple registers, a queue’s ability to solve consensus is completely dependent on its initialization.

There are many propositions/lemmas/theorems in this paper. And they are not limited to the queue object. I think it may contain what you want to know (I will read it carefully when I have time).

StackExchange Computer Science Q#43624, answer score: 6