Distributed Computing Q&A regarding the take home exam
More recent questions will be at the beginning (top) of the page.

Q:  May I assume that as with the renaming algorithm, when a single processor access the k-tight-group-renaming alone with <pID, gID> then the

response it gets is <pID, 1 > ?

A:  No.  At least I do not remember specifying the task that way

to solve the problem the processes may access the tight-renaming task in total k+1 times.  Each of course with a different pair of <prc ID, grp ID>.
If you have a solution only with a total of more accesses, then give it instead, it may give you some of the points.

Q:  1) why when i call the g-tight-renaming i task, i provide it with the process id? doesn't the result depend only on the group id?

A:   May be it is, may be not.  This is how it is built. The result may depend.

Q: 2) what happens if i call the renaming task k+1 times with the same group id but with different process ids?

CLARIFICATION:   A:  You may not do so.   This is in a k-tight-group-renaming

    which results would i get?

Q: 3) can i assume that the processes has unique names in the range of 1...k ?

A: yes

You can think about the g-tight group renaming as follows:  A task g-tight group renaming for x groups is a box with gx ports (legs).  The ports are grouped into x groups of g ports.
Now the only way this task may be accessed is with arbitrary pairs < process id, group id> such that
1.  all access to the same group of ports have to be with the same group name. and
2.  no process id appears in two pairs.  (i.e., each process id may appear at most once).

Q:  On the QA page you said that there are kx different ways to call the task. And I read that.  But I still don't understand how it addresses my question:  I asked what happens if the task is accessed more than k+1 times.   A:  The question only says that the task "may be accessed k+1 times", but does not specify how subsequent accesses might behave.

A: The question says, solve the problem while accessing the k-tight k+1 times.  k-tight group renaming behaves normally, i.e., returns a new group name to each of the kx possible accesses. 

If you cannot solve it with k+1 accesses give a solution with more accesses, if you can.

Q:  In Q4.C, it is not specified that algorithm A is a wait-free implementation of PS. I was wondering if this was neglected by accident.

A:  you are right !

Dead line extension.  Each of you gets now 2 extra (additional) days to turn in the exam.  I.e., the standard dead line is now 23 of June, and if you got additional days on the previous deadline, then you have them in addition to this new one.


in k-tight group renaming with x groups there are kx possible accesses, with many different pairs of <processor IDs and group IDs>.  Notice that x is at least two.  A  process may access the box with different pairs of <processorID, GroupID>.

default is a special output not from the input domain that signals to the process "could not reach decision".