Distributed Computing Q&A regarding homework #3
More recent questions will be at the beginning
(top) of the page.
Q&A Homework 3:
> In the class of 9.5 you
explained the solution for question 1 of Ex2.
> You used the following
argument: if the algorithm runs T rounds...
> You didn't mention what is T,
is it constant?
> What if T is a function of n,
i.e. what if T equals n^2, or even just n.
> When the algortihm runs on the
larger ring T is different from the T took on
> the smaller ring, thus the
argument of the T neighborhood fails.
> If T is constant it doesn't seem
to solve the question.
Since n is not known to
the processors, and the ring is anonymous then
they cannot tell. That is, in ring of size n1 they finish after
T(n1),
then on the ring I showed
in class they (some of the processors) would
again finish after the
same T(n1) although the ring size is 6n1 or more. Assume the action of
generating an output is irreversible, like typing the result on a printer.
> concerning ex. 3,question 1, i
have some questions :
> 1) do u ask for asymptotic
bounds ?
Give bounds as accurate as
you can. That is if you can compute the
constants, then do so.
> 2) do u ask for one algorithm
that stands in both bounds ( msgs and
> time ) ?
You can give two
algorithms.
> 3) can we assume that we have
an initiator node ?
NO
> I have the following question
regarding HW3 -Q2 :
> In this question we have
asynchronous ring.
> Can we assume that the delay on
the edges stays constant, that is if I send the same message on the same edge
twice it will take the same amount of time to reach the other side of the edge
?
> Can I assume that if I ran my
algorithm on n-size ring and it took X seconds, that if run the same algorithm
on the same ring it will take also X seconds ?
No and No.
> regarding question 2. When you
write n is unknown apriori, can we
> assume we have enough memory
(i.e. infinite), or that any solution
> that eventually uses memory
that increase according to n(i.e.
> counters, mapping of the ring
etc.) is not valid.
You should assume that
nodes have enough memory for counters etc that grow with n.
Regarding question 3b
in Homework #2 (bi-directional DFS in O(n) time). Some of you
correctly answered
that a processor may notify all its neighbors when it first receives the token
and at the time it
already forwards the DFS token to one of its not_yet_explored neighbors.
However, still many of
you lost points because you proof and analysis that this algorithm indeed takes
only O(n) time was
incomplete.
Clarifications:
The complexity of a
problem could be that it is unsolvable, i.e.,
that there is no algorithm
that can solve the problem in the conditions specified.
For example we proved in
class that 3 processors cannot reach consensus if at most one of them
is Byzantine, i.e., a
liar.
A randomized algorithm, is
an algorithm in which processors are equipped with a Random() function
which returns random
outputs. Specifically, if two processors
access Random which returns a random
value uniformly
distributed over some range X, then in each processor the output would be
independent of
the output at the other
processor.
Yes, consider message
compleixty more important.
> You ask for the best expected
time and message complexity, however,
> these may contradict each
other.
>
> Are we to provide two
algorithms - one for each, or are we to consider
> the message complexity as more
important?
> I have a question regarding HW3
- Q1:
> Except for showing lower bounds
on the number of messages and number of
> rounds, do we need to provide
an algorithm,
> which upper bound on messages
and rounds will be equal to the specified
> lower bounds ?
If your algorithm (upper
bound) will match the lower bounds that would be
the best. Otherwise, do the best you can.
> Do we need to provide ONE
algorith with both messages and rounds upper bound
> equal to lower bounds ?
> Or can we provide TWO
algorithms: one that has best messages complexity and
> the other with best time
complexity ?
You can provide two.
> - Question 3: that
> When you say the ring is of
size n, does this mean taht n is known to
> the ring nodes?
YES.
> Can don't really what do you
mean by 'randomized' leader election?
An algorithm that elecets
one leader when it terminates. However,
because the nodes are
identical (no IDs) the algorithm must use
randomization (flip coins,
make some radomized decisions like choose a
random number in some
range, where the range size is a function of n)
and then the algorithm may
fail
many times. So the complexity is only in expected terms.
> Regarding question 1 in the
exercise,
>
> 1. I assumed ids are
of O(lgn) - is it correct?
YES
Question 2C:
One possible answer for
the complexity, is that it is impossible.
Of course any answer has to come with a proof.
in the second question you didn't
mention the ring type i.e. is it
bidirectional?
A: Bidirectional
New question: can it be solved in a uni-directional ring?
in 2.a is the complexity is the 'bit
complexity' or messages?
Message complexity where
each message is limited in size to O(log n) bits.
and more general, in questions you
don't mention details what is the
default? i.e.:
1. the ring direction
bidirectional
2. fifo or not
fifo
3. how many of the nodes start the
algorithm (in case there is no leader as
in question 1).
Arbitrary number.
etc.
> regarding question 1:
> how does the algorithm start?
one node, multiple nodes?
Any subset of nodes may
start the algorithm.
Can you explain the symmetry
breaking marking in Q4(a)? What do you mean by
> ordering, does it only mean
that each node can devise between its neighbors
> because it knows the ID on each
of its links or it is something stronger, such
> as each node knows if it is a
left or right of its neighbor (i.e. if the
> neighbor marked it left or
right)?
Meaning, on each link
exactly one end of the link is marked as "head"
while the other as
"tail", or if you want, one is marked "red" and the
other end
"blue". A processor can check
its interface to each incident link
and see whether it is on
that end or the other of the corresponding incident
link.
>
> Btw, in Q4(b), you
wrote:"(a Las-Vegas algorithm, see definition below),...".
> The definition you mentioned is
missing. I assume it is the same as in any
> algorithm book.
A randomize algorithm that
always terminates with the correct solution,
but its running time
varies. THe expected running better be
bounded,
and in your solution, as
small as you can.