Distributed Computing Q&A regarding the homework
More recent questions will be at the beginning
(top) of the page.
Q&A Homework 2:
Again, unless it is specifically stated
otherwise, nodes have unique ids.
Remember also, that each message can carry at
most O(log n) bits.
And nodes initially do not know their
neighbors ids.
On question #2 you say "Use the dfs algorithm of the
previous section ( … with UNIQUE ID to each node)".
However, I see no place in question #1 allowing us to assume
there is a unique ID to each node.
So, in which subsections of #1 can I assume node ID's?
Another question, can I assume in 1)b. that each node knows
his neighbors ID's? (that's in case the answer for the question
Above is true for 1)b.)
>
Hello,
>
Regarding all the questions, where do we have to provide a formal proof
> for
correctness?
You
have to provide a formal proof
whenever
you need to provide a proof.
If
you take the two answers I placed on the
course
page, you can see the level of
formality.
The
essential point is to show me that you have
realized
and captured the key point of the proof.
> And
is there a need to provide a pseudo code algorithm
> or
is a general description of the algorithm enough?
Both. You need to provide a pseudo code, and
to explain
the
essential principle of how the algorithm works.
Shalom,
About question 1(c):
May I assume
that each node in the network has a unique ID?
[Yehuda
Afek] No need to. You can solve it without this
assumption, but a solution with that assumption is also okay.
Hi!
I'd like to
clearify some points regarding to the questions 1a and 1b in homework 2:
1. In the
description of the question 1 you wrote : "... initiates a token, which
has to visit all the nodes of the network, one at a
time". Does it mean that the only ONE copy of the token is permitted to
travel over the network?
NO. Only one token traverses the
network. However, it may send some
other messages around
to
assist itself in managing the traversal.
I.e.,
there is only one token, but not only the token may be transmitted
over
the communication lines.
2. Could I use
messages which don't carry the token in the algorithms 1a and 1b (for instance
ACK's )?
See
my reply to 1 above.
With regards,
its about question 1)c)
-------------------------
2) its is not clear what messages-complexity is
required in this question ?
THE BEST YOU CAN ACHIEVE
should it be proportional to the number of edges in
the graph (as in 1a) or to
the number of nodes in the graph (as in 1b) ?
OR TO SOME FUNCTION OF BOTH
i ask this because a theres a simple DFS algorithm
that works on either
directed/undirected graphs.
Hello,
another question:
in 1(b), after modifying the algorithm, its output
still has to remain the same? I.e., it is still DFS,
and DFS-tree is built?
YES.
Hello,
two questions:
1. In question 1, do I
have to show that the token
must traverse all the links on the network - in my
algorithm, or in ANY distributed DFS traversal
algorithm?
Your algorithm should make sure the
traversal is
a DFS like. I.e., there is some DFS on the network
that in some scenario would traverse the
network in the
same order that your algorithm ends up
traversing the network.
(and in any event all links are traversed
in such a traversal).