Distributed Computing Q&A regarding homework #4 Take-home exam
More recent questions will be at the beginning
(top) of the page.
Q&A Homework 4:
*** Take home exam new
due date: June 16th ***
Please
remember my instruction not to talk with other people. Some students were found to talk with other
people about the exam questions and therefore will receive zero in the exam. I hate to do it and please save me from this.
> I question 6:
>
> in the
Deq operation
> item
:= Swap(items[i]; pass);
> what
is pass?
> is it the same as item := Swap(items[i]; null) ?
Yes, you are right. Change it to
what you have suggested:
item := Swap(item[i]; null)
> A) Can I assume that the shared registers (Rab, Rbc, Rac) are
> initialized to some known value (null/0)?
Yes.
> B) May I add code lines to the double C&S that the processors
perform?
The C&S works as specified, you may use it as an instruction in the code
that implements the consensus (if it exists).
> C) Can any of the
processors fail ?
IT is a wait free system!!!
> D) If a processor can fail, do I solve the
question under the assumption
> of Wait-Free?
YES !!!!
regarding question 6. when
you define the sequntial specification of the
> fifo queue, you use
> act1
is 'before' act2. you mean that act1 starts and ends
before act2
> starts? i.e.
they do not overlap whatsoever right?
NO!
When I specify, and only when I specify, I assume each operation
occur in an atomic point in time. The actual behavior should be
linearized and after the linearization the
functional behavior should be
as in the specification.
Regarding Question 5b:
The double compare and swap works as two independent compare and swaps, each returning its return value, except that the two are serialized to happen at exactly the same instant of time. I.e., They take place atomically at the same point in time. Again, each of the compare and swaps functions as in the regular single compare and swap operation specification.
Question 5.b. - The Dual_Compare_And_Swap
> Is this operation equivalent to
two different, unrelated, C&S operations
> at the
same time - or if one of the compares fails none of the swaps
> occur?
The former.
Two working independently at exactly the same time.
> regarding question 6. when you define the sequntial
specification of the
> fifo queue, you use
> act1
is 'before' act2. you mean that act1 starts and ends
before act2
> starts? i.e.
they do not overlap whatsoever right?
NO!
When I specify, and only when I specify, I assume each operation
occur in an atomic point in time. The actual behavior should be
linearized and after the linearization the
functional behavior should be
as in the specification.
> Regarding exam
question 3, you wrote:
> "... implement
a shared virtual SWMR atomic register ..."
>
> Shouldn't it be:
...implement a shared virtual SWMR register ..."
> We're suppose to
proof or discard it's atomicy in 3b
!?
You are right
!
> In question 4B, can
we use MWMR atomic register or only SWMR atomic register (as we seen in class)?
MWMR are okay.
Copying from an article or
just mentioning it, is like copying from
a student. Meaning that if you read an article that deal
with the same question you are asked, then
you still need to answer it
with your own words as if I never read that article (which in my case is
true). And provide any necessary proof in its
fullness.
Q3a) Regarding
exam question 3
> Can you please rephrase the sentence:
> "If pi receives a message
"pi writes v" means i =/= 0 then,
it..."
>
> Shouldn't it read "If p_i... means i=0" assuming
p_0 is the single writer?
You are right, it should
be "means i=0"
>
> Q4a) Regarding
exam question 4
> Can we assume that a processs don't fail-stop during the execution of the
procedure ONE_TIME_TEST_AND_SET?
Rather than answering your
question I hint that : You are asked to provide
a "wait free"
implementation. !
> Q6a) Regarding
exam question 6
Your question (omitted) is
not phrased in a way i can answer.
The queue as specified is
a shared object that can be accessed by 2 or by
more processes concurrently.
> Q6b) Regarding Fig. 2
>
> The Enq
operation uses index 0 which is out of the items range. Either the F&A must
is defined as returning
the value AFTER the addition, or
counter is initialized to 1 instead of 0. In the later event, Deq should also
be changed to scan from 1 till m-1.
The F&A is indeed
returning the value of the object (counter in our case)
as it was * after* the
operation is applied to the object.
> 1. In Q. 6 there seems to be a
broken referance for an article by Herlihy and Wing
> can you correct it?
It is ref 47 in
http://www.cs.tau.ac.il/~afek/topics.ps
> 2. In Q. 1.
are the solution measured only on if they work or fail
or is there another (efficiency)
criterion?
Both. But at least 70% if it just work.