Distributed Computing Q&A regarding the homework


More recent questions will be at the beginning (top) of the page.

Q&A Homework 2:

> Hi Yehuda,

>

> It has come to my attention that tomorrow all classes end at 18:00 since its the Holocaust memorial day eve.

> Will there be a lesson ?

Not according to this:

 

http://www.tau.ac.il/calendar.html

 

I plan to have a regular class, tomorrow the 18th.  Notice next week, 25th of April we have no class (Erev

Yom Ha zikaron).

Yehuda Shalom,

>

> If i understand questions 1 & 2 correctly, i find that they are both

> can be answered in the same way. this is because in order for them to

> work (both problems) there must be a way to select a leader in the

> ring, but that is impossible in non-uniform rings. my question is, if i

> can prove that leader election is impossible, is that a satisfying

> answer?

No. Wrong.  Who said that inorder to solve these problems you need to elect a

leader?  Perhaps there is a way to solve these problems without electing a

leader.

Hello,

In question 3b can we assume that each node in the network has a unique id? and if so does a node know the id's of nodes connected to it?

 

No, it is not necessary to make this assumption in order to solve
question 3b.

I have a question about the 1st question of the 2nd assignment:

What happens when the input size is 1 bit? Can a processor check if it is the only processor in the ring? Is the "next" pointer equals to null? does it point to itself? If so, can it tell it points to itself?

No, a processor cannot determine whether it is alone.  If it still bothers you, assume the ring size is at least 2.

Hi ,

I have several questions about the second assignment:

- Regarding question 1:  I dont understand the possible input and output

of each processor p. (can the input be only streams of all zeros or all

ones? the output can be just one zero or one 1? ) Can you give an example?

The function is specified in the question.  You may assume that each processor receives one bit as input and all output the result of f(x1,x2,....,xn). 

- Regarding question 2: what is an orientation algorithm?

In AN ORIENTATION the ALGORITHM starts with EACH NODE MARKing ITS TWO INCIDENT LINKS

WITH R (RIGHT) AND L (LEFT), I.E., EXACTLY ONE INTERFACE R AND ONE L. 

INITIALLY THE NODES MARK THEIR TWO INTERFACES

ARBITRARILY WITH THESE MARKINGS.  IN THE END OF SUCH AN ALGORITHM (I.E.,

THE OUTPUT OF SUCH AN ALGORITHM) THE NODES SETS THE MARKINGS SUCH THAT

FOR ALL THE EDGES AROUND THE RING, ONE END IS MARKED L AND THE OTHER R.  That is they agree on a consistent direction of the Ring.

Many thanks,

Thank you for your previous reply. i'm still not clear about question

2, though;'even length rings' means all links are even (as in equal),

or even number of nodes (i.e not odd?)

"even length" means that the length is even, i.e., even number of nodes.

and in either case, i can't see

why it would be a problem for the following algorithm to run correctly:

if n is known and each node has an i.d, select a leader using some

leader election algorithm, then let the leader choose L and R, and it's

neighbors will choose accordigly (L if the edge was named R by the

neighbor, and R otherwise), and so on untill all nodes are covered. 

You are right, except that the nodes do not have an id (as in question 1), all nodes are identical.