Distributed Computing Q&A
HW 3
More recent questions will be at the beginning
(top) of the page.
Q&A Homework 3:
Another question
regarding 1(b):
“What is the complexity
of this problem if n is not known a-priori?”
Maybe I don’t understand.
If n is not known to the leader, it seems to me the leader cannot distinguish
between the following cases:
1) The ring’s length is 1
(he is the only processor with the link to itself) and the link is cut
2) The ring’s length is
20, the cut is somewhere.
I argue that if processor
output is based on input, then it will be stuck in case 1), because no message
will ever arrive.
Otherwise its output is
constant => will not be correct in 2 different cases of 2)
Where am I wrong?
Thank you again.
Assume the following: Before the algorithm starts each
node knows the id of its two neighboring nodes.
Hi
Yehuda,
Here
are some questions regarding hw3:
q. 1 Can I assume that when the
algorithm starts the cut is already there?
If not, how is the complexity of the algorithm
defined?
Yes, you can assume
the cut is there when the algorithm starts.
q. 1(b) “the
exactly same code” – it took me a lot of time to understand the code should not
be the same as in (a), but should be able to handle any ring size. I hope I am
the only one who has been confused.
I am sorry it took
you long, but yes, you got it right. "same code" refers to
the fact that the same code should run on any size ring (but it is a different code than the one of question
1(a).
q. 2 Is
there randomize number generator in each processor? Are those generators “bilti
tluim”?
yes and yes.
q. 3(a) “In
the homework you have proved that there is no ring orientation
algorithm
for anonymous rings of any size.” - we only proved for the rings of even size…
Right, but it has no effect what so ever on the
question!
q. 3(b)
I found no definition of Las-Vegas algorithm below.
“message
terminating randomized orientation algorithm” – could you please explain what randomized
algorithm is?
A randomized algorithm is an algorithm that uses
coin flips (random numbers) in its execution. Usually the randomization
is used to solve problems that are not solvable in a deterministic way, such as
orienting a symmetric ring. Now, there are two major types of randomized
algorithms, Monte-Carlo and Las-Vegas. In a Las-Vegas type, the
algorithm always terminates with a correct answer, but only its expected
complexity is bounded,
its worst case complexity may be unbounded. (In Monte-Carlo
the worth case complexity is bounded but the algorithm may terminate with
an incorrect answer - usually this happens with a very small probability).
Thank
you in advance,