More recent questions will be at the beginning
(top) of the page.
Q&A Homework 2:
Regarding
Q5c:
1. in 5c you are not restricted to have only token messages.
and
2. When there is a token, the token may carry any information on
itself, it can carry an id from one node to the next,
or even carry
one (or a constant number of ids) along a certain path.
לשאלה 5,
בסעיף א'
בקשת להראות
שכל אלגוריתם
שפותר את הבעיה
מקיים שהטוקן
עובר דרך כל
הקשתות.
מהן ההגבלות
על האלגוריתם?
האם הטוקן היא
ההודעה
היחידה שמותר לשלוח?
למשל, את
סעיף ב' פתרתי
באופן הבא:
ראשית בונים עץ
בעזרת
Broadcast and echo ואז
מעביר את
הטוקן דרך
קשתות העץ
בלבד.
אלגוריתם זה
פותר את הבעיה
אך לא עוברת
הודעת
טוקן על
כל קשת. למה
הוא לא חוקי
גם לסעיף א'?
מה
ההגבלות שהאלגוריתם
בסעיף ב' צריך
לקיים (במה הן
שונות מאילו שבסעיף
א')? האם
הפתרון שהצעתי
חוקי (השאלה
היא לא אם הוא
עומד בדרישות
הסיבוכיות
אלא האם הוא
עומד
במגבלות)?
מהן
ההגבלות
בסעיף ג'?
The
intention is that unless it is specifically said otherwise, there is only one token,
and it is the only message traversing the network. So what you did is not
allowed.
1.
For questions 2,3, and 4 – is the model
synchronous or asynchronous?
Asynchronous.
Notice that if you prove 2 and 3 for synchronous you have also proved it for
asynchronous.
2. In question 3, I assume that the processors are anonymous. This is not specified directly in the question, but it is hinted in question 4. Is this assumption correct?
RIGHT ! I should have
mentioned in Q 3 that they are anonymous.
In question 2 - "n copies
of p are arranged in a ring" - what is p?
A: p
is a generic name of processor from which a huge number of copies have
been manufactured. Recall that all copies are identical, there are no
unique names.
Also - what is the meaning of computing f(x_1, x_2, ..., x_n) when n is unknown? Does it mean that it should be possible to compute using a finite number of parameters?
as you
said, n is not known to the processors. n is given
here only for the presentation of the function.
In question 4b, it says
"give a message terminating randomized orientation algorithm (a Las-Vegas
algorithm, see definition below)", although there isn't any definition
below.
Where is this algorithm defined?
see
http://en.wikipedia.org/wiki
essentially,
it means that the algorithm stops only with a correct answer, but it may take
the algorithm very long time to reach such a state. The running time is
random, for any number of steps (amount of time) there is some probability the
algorithm with run that long. Of course, the longer it is, the much
smaller the probability. This is in contrast to Monte-Carlo randomized
algorithms, which have finite running time, but may stop with (small
probability) with an in-correct answer.
> in question 2:
>
> the processors has unique ID's ?(if so we can select a leader and finish)
> what do we know about the processors at all?
Right. Processors do *not*
have unique ID's. All processors are
identical, produced in a factory and then a ring was built from n
copies
of the processors.
> 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.