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.
CORRECTION 1:
In the collect, question 3, the algorithms should all be WAIT-FREE, like the inefficient simple one given at the
end.
CORRECTION 2:
In question 2, the system is asynchronous, there is no limitation on the relative speed of processes, and the algorithm should be WAIT-FREE, i.e., any of the processes may fail stop at any point of time.
***
Due to exams, Miluim and other reasons some students
submit the exam later than others.
Therefore,
even if you submit the exam already, please stay quite and do *not* talk to
others for at least one more week.
Toda
Yehuda
(Q3) > The question
asks for each collect operation to return a vector of the
>
values it read.
Is it enough that the collect operation print the
>
results? Or
perhaps whoever is running collect is supplying the
>
memory for the returned vector? If not, and we have to provide the
>
vector then there is a possibility that there were n
updates, all n
>
threads are running collect, all are more or less in
their last
>
elements. Then
each thread has O(n) vector, which means space
O(n^2)...
>
The question is about the space complexity of the shared collect
object, not the space taken locally by each thread. Each thread, individually may have $O(n)$ space locally without charging it to the total space
complexity. The local space complexity of
each thread is not counted.
Warning: Do not ask me questions of the form
“Can I do this and this <a description of an algorithm>” or
“I do that and this <description of a partial solution> and I have
this problem, is that okay?” If I
get from a student too many such questions (>1) I might stop answering this student.
> In question 1.b - can R be initialized to a non integer value , for example
> 1.25?
no and yes. If possible
try to stick with integers, but notice I did not limit the size of the
register. I want to know the consensus
power of fetch-and-add object without limiting its size.
(Q4) > Can we assume that the original Bakery Algorithm is ok (mutually
> exclusive, deadlock free, starvation free) and only prove that the
> replacement does or does not change any of these properties? Or do we
> need to prove these properties again for the complete algorithm if we
> reach a conclusion that that the replacement is ok?
Yes, you may assume the original is correct
and prove that all the good properties are either maintained or do not hold,
with the replacement.
Reply to Yael,
sorry but your questions 1 and 2 should have been very clear to any student
that
followed the material. There is no yes/no answer to them. The
algorithm
should be wait-free and correct as any shared memory wait-free algorithm we saw
in class.
The one day extension is for every student except those I told them otherwise
in
an email. What ever was your original extended deadline, add to it 24
hours.
(Q1)
the fetch and add register may not be initialized with a negative number
if you want to get all the points. If
you see no other way to solve the question then use negative numbers and you
may lose points because of that.
> is providing a pseudo code for the algorithms a must?
> I think the explanations of how the algorithm work are much clearer, and
> that code does not help the understanding at all, instead it obfuscates
> the algorithm with too much implementation details.
yes, both the explanation and the pseudo code are a must. You use pseudo-code in order to keep the
necessary details, sometimes the explanation may hide a critical detail which
is only revealed in the code. Pseudo
code is the only way we can make sure we are talking about the same
algorithm. Notice you use pseudo code
and not assembly, so you still keep a certain level of abstraction.
(Q1, Q3) you may assume that both n
and N are known in advance.
(Q3) Yes, you can assume you know n
in advance
> I would like to know if in Q3 we know n (not
just N) in advance.
> I think it's necessary to solve section b...
(Q3) > 1.
Can I supplay two algorithm one for the case k<logn and second for the
> other case?
only if you then know how to put them together (connect them)
into one algorithm, and show us how to do that.
> 2. In the algorithms can I use splitters? ...They are build of R/W registers
you can use any thing that is built from r/w
registers.
(Q3)
- is N (the maximal ID) known before
>
run time?
YES
(Q3)
> In
question 3 is it OK to return a set of elements <id, value>
>
instead of a vector that contains some elements that
aren't
>
initialized?
Yes.
>
(Q3) In the preface to question 3 you write the
definition of the
>
step complexity of a collect algorithm, and it seems
to me you have
>
here a circular definition. And I quote:
>
" The step complexity of a collect algorithm is
the worse between
>
(something) and the step complexity of the worse collect operation."
>
What exactly is the difference between a collect operation and a
>
collect algorithm?
In the question you implement a collect object (the implementation
is the collect algorithm). The collect
object/algorithm has two operations (methods if you will), store and collect (I
agree overloading “collect” is bad naming). So the complexity of the collect object is
the worse complexity between the complexity of the store operation and the
collect operation.
>
(Q4) Just to get it clear: N is the name-space size, n is the
>
number of proccesses and k
is the number of active proccess?
YES
(Q1) In question 1 it is enough to
deal with binary consensus (inputs and outputs are in {0, 1})
(Q2)
> In question 2, when answering that the registers may be initialized,
>
do you mean that they can also be initialized with the values proposed
>
by the processors before run?
No, no. Just may be
initialized by some value independent of what are the initial inputs of the
processors.
I.e., they may be initialized before the processors get to know what
their inputs are.
Similar question….
No way.
The inputs are given to the processors only after the system and
shared memory have been initialized.
All algorithms and solutions in
the exam are deterministic. That is, no
randomization is allowed.
Points distribution in the exam questions:
Q 1. 20% f&a
Q 2. 15% queue
Q 3. 30% collect
Q 4.
25% me
Q 5.
10% b/w
(Q1)
> In question 1, is it enough to show a consensus between the possible
>
process inputs {0,1}, as we did in the synchronized
case, or do we
>
have to show a consensus between arbitrary possible inputs, as we did
>
with compare&swap at
class.
What do you think? Looks like
I should have asked you to implement n value consensus from binary consensus.
(Q3)
regarding q3 in the exam:
>
If I answer section C do I need to answer section A ?
>
>
I ask this because the algorithm from section C subsumes the one from
>
section A
You are right. However, if
you use A in subsection C then we would rather see
A. But if you have a direct solution to
C without going through A then it is okay.
(Q4)
> In the assembly code of Q4, I am not sure what is considered an atomic
>
action:
>
for example:
>
number[local1] < number[local2]
>
is atomic? (memory to memory comparison) or only
register comparisons
>
is atomic?
>
>
Similarly, what about:
>
-- if statement?
>
-- (1 + number[local1])? vs. (1 +
local1)?
> -- etc.
All of these operations are on local memory. So in the comparison it would first read one
value to a local-register then the other and do the comparison, again locally.
(Q1) > Regarding Question #1: should we give the consensus number
> under specific initialization of the registers and v?
> or is v a number chosen by the processors?
v a number chosen
by the processors. Registers may be
initialized.
> In addition your clarification in the Q&A site
> confused me. As far as I understand (from the
> Herlihy’s paper as well), the consensus number for
> standart F&A is 2 under the assumption that v isn't 0
> (otherwise f(v) is the identity function). isn't that
> so?
The standard F&A that
supports f&a(i) for any integer i, has consensus number 2.
(Q2) In question 2: can I assume
that there's a NULL variable in the system,
and that 'dequeue' operation when the queue is null
will return that
variable? (that is, I want the processor that dequeues to know by the
return value that the queue is empty).
YES, dequeue
when the queue is empty returns the special code “empty”
can I assume that each processor knows if it is P0 or P1 and
so P0
may run a designated code for P0 and P1 may run a designated code
for P1 which is different from the code for P0
YES
Can
I relay on theorems that were not studied in class in my proofs?
NO, you have to prove them in your
exam.
(Q2)
Regarding the queue in question 2:
The queue supports only two operations on it: Dequeue and Enqueue. Both are
atomic. No other operation is provided
on the queue.
(Q1) . Is it true that the original
variant of F&A has consensus number 2 assuming that v is non-zero? If
v is 0, then a thread cannot know if it is 1st or not to run the
method.
I am not sure what you are asking, but here is some information
which you can easily find in the class notes, or in the literature: The consensus number of standard F&A
without any limitations is 2. In
particular see Herlihy’s “Wait-free
synchronization” paper.
Are there any limitations on v in question 1 (a) and (b)?
Can we assume it is never 0?
The only limitations are those
specified in the question, and the F&A register never starts with a
negative number. As to v, there are no
limitations, any Integer {.…-4, -3, –2, -1, 0, 1, 2, 3, 4, …..}
(Q2) Regarding question 2: Is
each operation on the queue atomic?
YES
(Q1) Reg Question 1: How are the
registers initialized?
You may choose how to initialize them.
(Q2) : Can i
present a two processor consensus algorithm which used two queues that are
initially empty end R/W registers?
Only
if you cannot do it with one queue and you may lose some points.
(Q2)
Can we initialize the shared read/wirte registers ?
YES
What
type are the registers ? (SWMR,MWMR...).
You may choose.
(Q4)
Do we have to prove only mutual exclusion, or also other properties such as
deadlock-freedom, starvation freedom ?
Also deadlock freedom, starvation freedom.