Distributed Computing Q&A regarding the Take home Exam
More recent questions will be at the beginning
(top) of the page.
In most cases I do not reply to
your emails with the questions but rather put the answer below. If you sent a question, check this page for
the answer.
Yet, one more, and last Exam extension: Every body gets an extra 24 hours on his /
her deadline to submit the exam.
New standard
deadline is June 20 4PM.
Farther
clarification for Q5:
The maximum that may access is n, but the
splitter should split also if only k < n arrive.
What is the minimum
required in Q4:
In class we saw the
two process version of BG agreement. You
have to
generalize this BG agreement to 3 processes in full detail. (Pseudo code,
proofs).
As for the rest of the simulation, explain the differences from the one we saw
in calss. Where "explaining the differences"
means: (a) describing the
original and why it works, then (b) describing the difference and why it still
works. Explanations should be
clear and should not miss any required detail.
In any event, you should start with a short paragraph giving the key ideas.
Q5: The splitters in q5 have no stop exit.
Q5: n the maximum number of processes in the
system (and that may access the splitter) is known.
Q5: splitters should be wait-free.
> In question 1.c., can I assume
that the size of the register is bigger than
> f? |R|>>f
Any size you want
Yes and no. I.e., for the f&a and
swap you have one initialization to zero operation "for free".
Alternatively
assume that all objects are initialized to empty (queue and stack) or zero
(f&a and swap)
value by the factory. All other initialization that is being done, is on the account of
f.
> Question regarding 1.: Is it right, that the inialization of Bounded
F&A and Bounded Swap is not
> counted in f operations, which we can do, differ to
stack and queue initialization?
> Because if yes, and f=1, we cannot use the register, cause
it's already overflowed.
Yes, n the maximum
number of processes that can access a PS, is known in
advance.
Regarding 5c,
> when it is written - "let
A be an arbitrary PS ... for n process". it is
> meen that PS know for advance
the number of process which will enter
> it(which is n)
Exam
extension: Every body gets an extra 24
hours on his / her deadline to submit the exam.
Few clarifications,
that may be required in the exam (you may have solved the exam without them)!!
:
1.
You may assume the following known fact: There is no read/write atomic registers adaptive
renaming algorithm in which, if k processes have arrived then they are given
new names in the range 1, …, 2k-2. I.e. with no name larger than
2k-2. (In class we stated the
non-adaptive version of this, and I believe we also stated the above, which is
repeated here for clarification).
2.
If you look at the literature you will find that there is an optimal
adaptive renaming algorithm (wait-free and in the read/write atomic registers
model), that if until now k processes have arrived, it re-names them with at
most 2k-1 names. E.g., http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=301335
Hagit Attiya, Arie Fouren: Adaptive and Efficient Algorithms for Lattice Agreement and Renaming. SIAM J. Comput. 31(2): 642-664 (2001)
Yehuda
Afek, Michael
Merritt: Fast, Wait-Free (2k-1)-Renaming. PODC
1999: 105-112.
3.
Question 5a, prove it for any n>2. (For n=2 the claim is correct with additional
assumptions).
> if I want to initialize the
stack(or the queue) to contain some elements.
> are this elements count in the f operations (of push or enqueue) that I
can
> do?
Yes.
> It doesn't clear what happens when only 1 process arrives the splitter:
> If it exits from the first leg then we have an empty
set for the second leg and
> ALL the processes exit from the first leg.
Assume the
condition must hold in all runs in which more than 1 process have been participating.
> What are the supported operations of these objects?
Queue: enqueue, and dequeue.
Stack: Push and pop.
NOTHING
Else. The above are atomic with the usual
definition.
> Can I Read from these objects without pop/dequeue?
NO
> If not, what does initialization of such objects
mean?
Means that they
start (initialized) before any of the code starts running with the specified
initial state.
>
> Does it mean that an initial value is inserted
Possible.
> Are push/enqueue operations return any value?
Return an ok
response when the operation finishes.
> I would like to receive the interfaces of the
> objects in question 1 (if a
queue has head\
> action is critical),
queue supports only enqueue and dequeue.
stack supports only push and pop.
Nothing
else.
Each of enqueue, dequeue, push and pop are atomic and acording to the
standard definition.
> and another thing, it seems
obvious but the
> flag in question 3 is
initialize to false right?
Yes
In solving the exam
you may use results stated in class without proving them, unless you modify the
proof, or the result, that was studied in class.
> i have a few questions regarding Q5:
> in section a - does the splitter have no "win" exit? just two partitions,
> which can take at most n-1 processes and no less than 1 process? please
> correct me if i'm wrong.
First question of
the type "correct if I am wrong" are not allowed.
The splitter has
two exists, you can name them any name you wish.
> in section b - same question here - no "win" exit? also, in our
> implementation, are we supposed to use only *regular* registers, or can we
> use atomic registers here as well?
read/write atomic registers.
> In question 3, what are the exact properties of A - specifically:
> < snipped text>
You can assume on A whatever is writen in the question. It is an arbitrary mutual exclusion
algorithm in which the exit code has a wait
statement.
> Can the entry or exit code of A wait <again snipped text>
The behavior of processes are as we discussed in class, and are
independent of what you assume
on A.
> <more snipped text>?
Again, make no assumptions on A other than those in the question.
>
> In section 5c, can I assume the PS object is wait-free?
yes.
> Question 1
>
> I don't have the specification of swap (I've participated in all the lessons).
> Is it the correct specification for swap:
>
>
swap(R,v)
> old := R
> R := v
> return old
YES. All of that is done in one atomic operation.
>
>
> Question 1b
>
> Do you mean that f is the SAME for all F&A objects (i.e. every two F&A objects
> have the same f) ?
At the same
instance of the problem f is the same for all copies of the object. I.e., at a particular run time of the
algorithm all copies of the object will have the same f.
> In sections 1a,1b,1c :
> If I think the objects~R consensus number is infinite ~V can the algorithm in the
> proof use knowledge of the number of participating processors (n)?
Read the question. I
specifically addressed this in the question.
> Can I initialize the objects in section 1a (particularly queue and stack) to
> any value other than empty?
Yes.
> Can I initialize the objects in sections 1b and 1c to 0?
Yes.