Distributed Computing Q&A
Take home exam
More recent questions will be at the beginning
(top) of the page.
1. Is it allowed to use
an atomic register that can store more than one bit? (e.g., a 2-bit register).
Yes. Any finite size reg is okay.
2. Assuming that the
answer to 1 is yes, and I have a 2-bit register, can I atomic-write to one of
its bits only? (e.g., atomic-write to the right bit only).
No. Unless you show how to construct this from atomic
read/write registers.
I have
several questions regarding question 2 in DC
final
exam:
In class
we talked about distance vector algorithm
problems
such as "looping to infinity" and ways to
solve
this problem, like sending the complete path to
a node
upon a change.
(a) Should
my algorithm take in account "looping to
infinity"
problems?
(b)
Continuing from last question, does a message
contain a
line record of the distance to each neighbor
or that
information plus the entire path?
(c) By
"algorithm message complexity" do you mean the
total
number of bits sent in order for all nodes to
initialize
their entire routing tables or the total
bits of
messages sent following a single update?
I have
some questions about the exam:
1) In
question 2, I don't understand why the single
weight
distance vector algorithm takes O(n^2E). Is it
because
its idea is similar to applying n times (e.g.
the
number of vertices) the Bellman-Ford's algorithm
for each
vertex ???
most
n times (one time for each improvement in the
distance).
2) In
question 2, even if the single weight distance
vector
algorithm takes O(n^2E), I don't see the point
in the
algorithm, where we used the weights of the
edges (It
seems to me as the algorithm is generic,
i.e.
built to any weight).
Right. But when the weights are not all the
same (=1)
then
the complexity may be different.
The maximum
distance
is not n.
I
have not mentioned in class universality of objects with consensus number 1.
You
need to construct the object from atomic read/write registers. These
are
the read/write registers we discussed in class.
-----Original
Message-----
To: 'Yehuda Afek'
Subject: RE: DC exam
Can
you please elaborate some more, I do not fully understand what "from
atomic registers" means.
Can't
atomic registers implement ANY object with consensus number 1? So by showing
that a certain object has consensus number 1
if
follows from universality that it can be implemented by ANY other object of
consensus number 1 (among those objects are atomic registers) ?
-----Original
Message-----
From: Yehuda Afek [mailto:afek@tau.ac.il]
Subject: RE: DC exam
"from
atomic registers"
-----Original
Message-----
To: 'Yehuda Afek'
Subject: RE: DC exam
Hi Yehuda,
In question
3 - Is it suffice to prove that the consensus number of the gs object is 1? and
say that since it has the same consensus number as atomic registers then it can
be implemented from them in a waitf-free manner without showing the
implementation itself?
this
is impossible with read/write registers.
it
is a stronger operation.
-----Original
Message-----
To: 'Yehuda Afek'
Subject: RE:
Well i don’t want any body to complete a change
to the reg while i do a xor, and this is inorder to not overwrite it's write
with my value.
So i want to read the value and to set it , in
the same op.
-----Original
Message-----
From: Yehuda Afek [mailto:afek@tau.ac.il]
Subject: RE:
Does the xor return anything?
If not why not just read REG into tmp,
Xor with tmp into result
Write result.
It will all be sirializable at the write
operation.
-----Original
Message-----
To: afek@math.tau.ac.il
Subject:
Hi
Can i have xor op, which is atomic. so i take the reg and
xor it with a fixed value , and no other write op can be in the middle of my
xor op.
I have a
few questions regarding Q2:
1)
Routing tables include IDs of routers or IPs of routers ?
(in the secound case each router
may have more than one entry?)
In
our case each row in the routing table at node v includes the destination id
(router name)
and
the distance to that destination.
Each time there is an update in a subset
of
the rows, that subset only is sent to all the neighbors.
2) Is it
FIFO ?
yes
3) When a
node sends update, does it send it's entire table or only one line ?
Only
the lines that are different.
4) When I
have two values of weights, is it 1 and 2 ? Can it be 1 and 10 ?
Could be either of these, or any two positive
values.
Regarding
Q5:
For the implementation to work
correctly, it means that the first processor that calls the procedure
ONE_TIME_TEST_AND_SET
is the one that gets a return value 0 and all others get 1???
No.
The T&S is atomic (i.e., sirealizable)
i'll
rephrase my question on 5:
can we asume
anything on the given "2-process T&S objects" (i.e
correctness according to what we learned in class about T&S. or
just what is stated in the question "... the first T&S operation
returns 0 and all other 1"
Correctness according to
what we learned in class. Atomicity (which means sirializable)
Regarding
question 1:
You said
that each node knows the weights of it's
adjcent
links. Does it also know which node is at the
end of
each adjcent link?
each
node know which node is at the other
end of each adjcent link
Q1:
1. Are
the weights on the link unique?
not
necessarily.
2. Does a
node know specifically the names of the computers adjacent to it
(not only
the weights on those links, but also who is on the other side)?
yes
Q2:
Are the 2
possible values positive? Isn't there a danger of a loop
otherwise?
Q3:
What
exactly is the labelling? can it be a write operation that we choose
(e.g.
writing 1 to Q/P reg)?
If
you try to implement it, you may implement it in any way you think
is
good.
Q5:
1. in the
"sequential specification", the meaning is that the first return
value of
T&S will be 0 (not necessarily the first process entering T&S)?
Kind
of true.
2. B - Is
the meaning of the previous question that while the 0 is not
returned
no one returns 1?
How does
it stand with the wait-free demand (if
the
winner fails, all are stuck)?
3. C -
deterministically?
Question
regarding Q1:
Can it be
supposed that the weights of the links are unique?
no
1) question
2: Can one of the weights be "0" , or not an
integer ?
0
- no. For simplicity assume all weights are integers.
What do you
mean by message complexity in this case?
It is the
amount of rout tables excanged between the routers (nodes) until they reach to
a point in
which all the rout tables in all the nodes are stable and no more change?
Each
message may contain one record (entry) in the routing table (e.g., one line
of
the table).
If I want
to use algorithem that been taught in class,
should I
explain it and prove everything or
for
example can I say that Finding Leader in
graph
when all the processors are cycle in the
asynchronous
case is running in O(nlog(n))?
Depends
on the algorithm. The classical
such
as
leader election on a ring you can assume you
have it as a black box.
Regarding
Q1:
Are the
wieghts of the links are unique, which is no two links with the same wieght?
Not
necessarily.
Regarding
Q4
Does
1/some/all of the processor/s start the algorithem?
Any
subset may start.
is it
possible that the matching won't be between 2 processors
that has
link between them in the circle?
No,
only immediate neighbors may be matched.
Regarding
Q2
Every
message that contains your distance vector and send to
other
node is count as 1 msg of as n msgs in the algorithem
message
complexity?
I
suggest each time you send a table of size n you count it as
n
messages. But notice a node sends
to its neighbors only the
entries
in the table in whcih there was a change.
Rows in the
table
that do not change are not transmitted to the neighbors.
question 1:
"...need
to know the MST "
what if
there are many (say all weights are equal)
is an answer
that each node knows a MST good enough or should they all agree on the
same MST?
Should
agree on the same.
another question for 1: is it safe
to assume a node knows from which link he got a message? (like different
ports)
YES.
Regarding
question 2:
Could
you please repeat the argument for the O(n^2*E) complexity? It was
very
brief in class.
Very briefly, since it is loop free, each destination may improve its
distance in the routing tables of other nodes n times, from infinite
(=n+1)
down to at best 1 in n improvements. In each improvement each of the
other nodes updates all its neighbors about the improvement. Thus, per
destination you get n x E.
Now since there are n different destinations,
i.e., each node is also a destination, you could at most reach n^2
E. Notice
we did not try to argue it is a tight upper bound, only that it is
an upper bound on the case of distance vector in a network where all
weights
are the same.
Regarding
question 5a:
In
class you explained the "waitfree model" as a model where processors
cannot
wait for other processor, but will all eventual reach termination.
This
is equivalent to the n-1 stop-fail model, only that in the later,
processors
can stop-fail and not reach termination.
Here
it seems that in the 1st model the code will work, but not in the
second.
Which one did you mean?
These two models are equivalent.
We can not "force" a process to
make enough steps to reach termination. We only guarantee that a
process that will make enough steps will reach termination, independent
of any other process taking steps.
Question
1:
When you
say "On each link at each time unit, only one message with one edge
weight
and one node name may be transmitted", do you mean unidirectional
link
(that is, between every two nodes there are two links, one for each
direction)
?
Yes,
I should have written "only one message in each direction...."
Question
4:
Is the
ring synchronous?
no
Question 1 - At the end of our algorithm does every
node need to know the MST or only 1 of them? If every two neighbors are
connected with 2 links,
one for each direction then in the end of my algorithm every node knows the MST but if there's only one link then the only way i can solve
it is that only 1 node will know at the end what is the MST.
At the end of the algorithm all nodes should know all the MST.
Question 1 - Do we have to formaly prove that in order to calculate MST one should know the exact topology of the network? or is it suffice to say that
since some node cannot know the topology it cannot calculate the MST ?
You need to show that it is impossible for all nodes to know all the links of the MST (which is less than knowing the entire topology).
Question 1:
When you say "On each
link at each time unit, only one message with one edge
weight and one node name
may be transmitted", do you mean unidirectional
link (that is, between
every two nodes there are two links, one for each
direction) ?
Question 4:
Is the ring synchronous?
q2: I know we pass
it in the class, but, seriously, I can't understand why
the trivial worst
complexity of
distance vector is O(n^2 E) given the same weight on the edges
Is that complexity
of the messages? Time complexity? What is the message?
Can it be as big as
the routing table?
There is a
centence "asynchronous means event driven,..."
Does it mean that
it is spoken of different "asynchronous" to what we are
acustomed with?
"Give an
example network where such a complexity is materialized":
Is there some
restrictions to example given, like E=O(n^2) etc.?
Or can we use the
"sroh", full mesh, some other special case as an example?
q4: Is the ring
synchronous?
If the processors
do not know N,
should the algorithm
be message terminating?
As I understand
the question,
"maximum
matching" means all the processors will be arranged in pairs.
Am I right?
I'll formulate my first
question again
I' meant to ask wheter
there can be situation
that
one link in the network will stop working,
so the distance between 2
nodes, u & v will change to infinity?
and to be sure that the
only initator of such an update in network
operation can be change in
the weight of one or some links?
2)In question 4, I did not
understand at all
the decleration of a
neighboring pairs.
Regarfing to Q2
1) Does the only possible
change in the network is that
a link weight can be
changed from 1 value to the other,
I mean no possibility to
throw link out of the network
(then u might have looping
to infinity problem)?
2) I can assume that the
nodes don't have any network
tree? (and effcors don't
have all the network infomation
and then they could build
the tree)?
is it safe
to assume that Wij=Wji?
YES
question 1:
In
(c) you say that "...at each time unit, only one
message with one edge
weight and one node name may be
transmitted..." -
what do you mean by that ? Do you
mean that if we have a
X-weight (X is a natural
number) edge then it will
take X time units to a
message (of O(logn) size) to be transmitted to the
other side ???
question 2:
What do you mean when you
say "...such a complexity is
materialized..." ?
Question
2: can I assume weights of final precision, specifically coded in
O(log
n) bits?
Question
3: Is there a tautology?
...
s0, from which it moves to state s1 if P performs a label, and from
which
(**s0**) it moves to state s2 if Q performs a
label. **From s1 it moves to s2
if
Q performs a label operation.**
Is
there some typo? It seems the question should be revisited.
Question
4: It's homework 3 question 3. Is it the bonus question? If it is,
do
we get our hw3 checked back before returning the exam?
That is a typo. This
question is not part of the exam.
New exam on the web site !!!