More recent questions will be at the beginning
(top) of the page.
Q&A Homework 2:
CORRECTION:
> Regarding question 1b (non-FIFO snapshot) in HW2:
> Are we allowed to attach a "header" to each message so that it arrives
> with the message (i.e. the header becomes part of the message and they
> never get separated on the channel)?
You may mark messages of
the original algorithm with some constant number of bits.
> Is it enough to describe the algorithm or should I write down the pseudo code
> for algorithm as well?
You need to describe it
(short description with the key ideas) and
Pseudo code, clear and
short.
> In 1b, Can I delay messages ?
NO
> I want to send a snapshot message on a link, and then delay messages from being sent on the
> same link until
> I receive a suitable ACK.
This violates the
requirements.
> 1. in question 1b - are we
allowed to delay messages of the underlying
> algorithm? That is, is a
processor allowed to store messages it is
> supposed to send according to
the underlying algorithm, and send them
> only when it receives some kind
of "ACK"?
NO
>
> 2. In question 1b - do we have
a way to send an ACK that refers to a
> specific message of the
underlying algorithm? That is, can we assume
> that each message of the
underlying algorithm has some unique
> information, and we can extract
it and send it in the ACK?
YES
> 3. In question 3 - according to
the model in the question do all the
> processors that perform an
orientation algorithm start at the same time?
In some runs they all
start at the same time, at other runs they may start not at the same time. The algorithm should work for any scheduler,
i.e., in both cases.
> 4. In question 4b - can we
increase the complexity of the number of
> messages in the algorithm when
we decrease the time complexity?
Not (Certainly not in the
big O).
> 5. In question 4c - can we
assume the processors have unique ids?
It could be solved without
unique ids (of course the initiator is singled out). If you do not see that solution, then give a
solution with unique ids.
> Regarding question 1b (non-FIFO snapshot) in HW2:
> Are we allowed to attach a "header" to each message so that it arrives
> with the message (i.e. the header becomes part of the message and they
> never get separated on the channel)?
The answer is no. In order to solve the question it is not
necessary to attach any bits to the messages of the original
algorithm, of which we
take snapshot.
> in question 3 about the orientation algorithm, can I assume that all the nodes
> of the ring are identical (so there is no difference at the beggining between one node and another)?
You are right, we have to
assume all the nodes are identical, i.e., no unique ids.
> For 4b - can we assume the channels
are FIFO?
Yes.
> 1. In question 2 - do the
processors know n?
NO
> 2. In question 1b - should the
modified algorithm have to include
> termination detection? do we
have to write pseudo code for the termination detection?
Either pseudo code, or a
call to some other algorithm that we know and that would do it for you.
> 3. In question 4b - if we have
times at which there is more than one
> message on transit, what is the
definition of a DFS traversal, because
> DFS requires a certain order on
the arcs that are visited, and if we
> have many messages at the same
time - there will be no such order.
> In other words - what claim
should we make about the algorithm in
> order to prove it performs DFS?
It should still be a true
DFS tree. I.e., there is a DFS traversal
of the graph which would result in that tree.
> in question 2,
>
are all the messages that the processors receive consist of 1 bit or
> any number of bits?
Any number of bits
>
can I assume that the processors have limited amount of memory?
Yes
>
does the function f handles input of any size?
The input is of size n,
not known to the processors.
1. In question 2 - is the model an asynchronous network with bidirectional
connections between the nodes?
Does not matter
2. In question 2 - does a node know which of its 2 neighbors is the right one
and which is the left one (or in other words - does it know which one of its
neighbors has a number smaller than its own although it does not know the exact
numbering)?
Again, does not matter
3. In question 3 - what is an orientation algorithm? (or perhaps we will study
it only next week?)
see below
4. In question 4 - if the network contains a node "a" that wakes up
spontaniously and has 2 neighbors "b" and "c", and b and c have another common
neighbor "d", what is the tree should the DFS traverse (possibilities are
a->b->d->c, a tree where both b and c are sons of a and d is a son of one of
them, etc.)?
or perhaps it does not matter as long as the tree is traversed in DFS order?
Should be a tree that
results from a DFS traversal from the initiator. Not all the trees you describe above are
such.
I have a question regarding q. 3:
I would like to know what is exactly an orientation
algorithm.
In AN ORIENTATION the
ALGORITHM each node marks one of its incident links R (right) and the other
with L (left). Initially these markings
are arbitrary, that is there could be links that both ends are marked L or both
marked R or R & L. AT THE END OF
SUCH AN ALGORITHM (I.E.,
THE OUTPUT OF SUCH AN
ALGORITHM) THE NO
FOR ALL THE EDGES
AROUN
Question number 2
Can you explain what means that computing begins at each processor and each
proccesor should output the f(X) ? Because ecah of them recieves only one bit
and the result of calculating of f(Xi) (where Xi the bit which recieved the
processor with number i)it is 0 or 1 but the result of calculating of f(X) it
is 0 or 1 too,i.e mean that they unite their result or they exchange by theirs
Xi or something else?
The function is specified
in the question. You may assume that
each processor receives one bit as input and all processors output the result
of f(x1,x2,....,xn).