5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ it would be helpful to give a ref. Wait-free synchronization / Herlily. also its hard to understand the question exactly. an algorithm that starts off with empty queues & then pushes empty values at the front is also starting off with an empty queue, isnt it? so maybe that needs to be rephrased more exactly? $\endgroup$
    – vzn
    Commented Jun 18, 2015 at 15:01
  • $\begingroup$ You're right that understanding the subject of the paper is necessary to solve this, but the question as phrased is well defined. I don't understand what you mean by pushing empty values, but the primary issue is that if the algorithm starts by writing a value into a queue, then upon dequeueing a processor can't know whether the other processor had already dequeued. So we have to do something more subtle and utilize more than one empty queue. If you propose a specific algorithm I could tell you what's wrong with it. $\endgroup$
    – ctlaltdefeat
    Commented Jun 18, 2015 at 15:23
  • $\begingroup$ sorry typo that should be written "pushing initial values to the (front of the) empty queue". apparently there is a central queue that is shared by each process but no process has its own queue? a bit more of a sketch of that would be helpful. also defn of basic terms eg "wait free consensus" etc. the consensus # is apparently a concept of Herlilys framework/ hierarchy. $\endgroup$
    – vzn
    Commented Jun 18, 2015 at 15:53
  • $\begingroup$ is the prof hinting at sec 3.4 the augmented queue with peek operation (queue initialized to empty), or is that ruled out? $\endgroup$
    – vzn
    Commented Jun 18, 2015 at 16:06
  • $\begingroup$ Updated the question with more explanation. We are not allowed to use queue with peek, although we can (and in fact need to I believe) have more than one empty queue. Processors can operate on every queue in memory, we don't have to restrict processors to their own queue. $\endgroup$
    – ctlaltdefeat
    Commented Jun 18, 2015 at 16:47

3 Answers 3

Reset to default
6
+50
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't have access to the first paper $\endgroup$
    – ctlaltdefeat
    Commented Jun 19, 2015 at 10:46
  • $\begingroup$ @ctlaltdefeat Write me an email (please find my email address in my profile) and I will send you a copy. $\endgroup$
    – hengxin
    Commented Jun 19, 2015 at 11:42
2
$\begingroup$

did not find this in a published paper/ ref so far, however here is a similar exercise 2b with the basic structure of the algorithm outlined (with only one small missing piece.)

Assume now that you do not have this initialized queue, but rather you have two initially empty queues. Take a look at the (incomplete) algorithm proposei(v). Each process initially has a private input value v. In the algorithm, each process first enques a winner and then a loser ball in “its queue”. Complete the algorithm with the notation of the function funci(Qj , Rj , v) so that proposei(v) reaches consensus even if up to 1 process may fail. Make sure that you go through all the different executions and check whether they give a correct result.

Algorithm 1: proposei(v)

Input: v ∈ V, i ∈ {1, 2}; processes pi ; empty queues Qi ; register array of size 2 Ri [1, 2]; initially false flags flagi
1. Qi.enq(”winner”);
2. Qi.enq(”loser”);
3. flagi.write(true);
4. resulti = v;
5. for j = 1, 2 do
6.   if flagj == true then
7.     resulti ← funci(Qj , Rj , resulti);
8. return resulti

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks, my googling has failed me this time as I wasn't able to find this. I'm trying to think how to complete this. $\endgroup$
    – ctlaltdefeat
    Commented Jun 18, 2015 at 19:24
  • $\begingroup$ I believe there may actually be an error and line 4 needs to read "$R_i$.write(v)". In this case I believe we can define funci(Qj , Rj , resulti) to be: deq Qj, if it's winner return "v" otherwise return $R_{1-i}$.read(). What do you think? $\endgroup$
    – ctlaltdefeat
    Commented Jun 18, 2015 at 19:28
  • $\begingroup$ suggest (as written) making a table of all possibilities in the queues & algorithm flows/ time sequences. & note there may be more than one solution to this problem... possibly either inside or outside the template... & btw think this has probably been published somewhere... $\endgroup$
    – vzn
    Commented Jun 18, 2015 at 20:06
  • 1
    $\begingroup$ @ctlaltdefeat Maybe check the second paragraph of Introduction of this paper. $\endgroup$
    – hengxin
    Commented Jun 19, 2015 at 1:29
  • 2
    $\begingroup$ @ctlaltdefeat This paper has also studied the problem. $\endgroup$
    – hengxin
    Commented Jun 19, 2015 at 1:50
2
$\begingroup$

There is a generic construction that turns a consensus algorithm for n processors that uses initialized objects into a consensus algorithm (for n processors) that uses n uninitialized copies of the same objects. By applying this construction to the 2-processors consensus algorithm that uses an initialized queue, one obtains a 2-processors consensus algorithm that uses 2 empty queues. The algorithm obtained has the same structure as the partial solution in vzn's answer.

The generic construction is described in Section 3.1 of Elizabeth Borowsky, Eli Gafni, and Yehuda Afek. "Consensus power makes (some) sense!." Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing. ACM, 1994.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.