Distributed Computing Q&A regarding the homework


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

Q2:

You need to provide a wait-free solution

1. In question 3, do we have to use SWMR registers, or may we use "regular" MWMR registers?

 

May use either of them

Q4:

You need to describe it very clearly, and in detail.  Then you need to argue (not a formal proof) why it is correct.  All the key points of the proof should be included, but no need for a full formal proof.

Q3(e) you may assume processors know n

Q3(d) l (ell) should be O(m2) and NOT O(n 2) !!!

Q2

It is allowed to use the process’s ids.

Q5

Does the "decide" operation terminate the execution? If so why is there an assignment to propi right after it?
I need further clarification to understand the exact semantics of the programs:

After deciding each processor continues execution and sends his prop value to all others processors in the following rounds?

 

YES, processors do not stop execution after deciding

I have a few questions regarding the computational model of q. 2:

1. Are we allowed several F&A_PC registers?

yes

2. Are we allowed any additional shared memory?

R/W registers

 or any other normal F&A registers?

No

1. In the line that says "Receive n - f round r messages...", what happens if all n processors send messages - does each processor get and store only the first n-f messages it received (and disregards the rest)? Also, does the subscript on prop mean anything (e.g. the index of the processor it was received from), or is that just the order they were received in?

 

It waits to receive n-f, when n-f have been received it proceeds.

subscript does not mean any thing, in particular no relation to the process names.

 

4. Does a processor stop running the algorithm after it decides?

 

No

Question 5

1.       Are we talking about fail-stop failures or byzantine? I think that in class you said byzantine,
but I don't see how it makes sense together with receiving only n-f messages in each iteration, that is not receiving messages from the faulty ones.

 

Assume only fail-stop failures.

  1. In 5a, do we need to provide a proof?

yes (together with section b)

Question 3

1.       In 3a, what do you mean by "Prove that the consensus number of the tight group renaming problem is at most g"?
Do we need to show that give an algorithm that solves the tight group renaming for g groups, we cannot make a consensus of more than g processors?

I am going to publish a new 3a which replaces the above.  I.e. 3a is going to be a different question.