Graders report for HW 4 HW 4 Part a Question 1 ------------------------------------------------- 0. Average: 9.8 1. Grading Policy: 8 points for describing general situation 1 for a trace 1 for an explanation of why the trace is not in G 2. General comments: Everyone basically got this question correct. Points taken off are more representative of not having a complete solution written down. HW 4 Part a Question 2 ------------------------------------------------- 0. Average: 9.5 1. Grading Policy: 8 points for describing general situation 1 showing that the situation goes on indefinitely 1 showing that this situation represents a fair execution 2. General comments: Everyone basically got this question correct. Points taken off are more representative of not having a complete solution written down. HW 4 Part a Question 3 ------------------------------------------------- 0. Average: 8 1. Grading Policy: +2 if the two correct formula is used (already in the textbook) +1 communication complexity: 2m+O(r(n+e’)) +1 time complexity: O(r(c+O(hd)+O(hl))) +5 if communication complexity is correct. +1 the edge length of a cluster is correctly calculated +1 the path length between two end roots in a row/column is correct +2 the communicate path between all roots is correct +1 final communication complexity is correct +3 if time complexity is correct. +2 two cases are analyzed, or state the height in an upper bound. +1 final time complexity is correct 2. General comments: Most people use the formula 2m+O(r(n+e’)) and O(r(c+O(hd)+O(hl))) in the textbook, and figure out e’ and h. We should consider the best case that roots are in the center of each cluster. In this case, e’ is 2(k-1)*sqrt(n); there should be two cases for h: when sqrt(n)/k is even, the height should be sqrt(n)/k; when odd, sqrt(n)/k-1 (it doesn’t affect the final complexity). Some people analyze separately the Alpha case and Beta case and combine them. The common mistakes include: 1. Mistake k as the edge length of a cluster. 2. Misunderstand or get a wrong e’. 3. Consider a worst case in h, not the central case. 4. The analysis of the height of a cluster tree is not complete. HW 4 Part a Question 4 ------------------------------------------------- 0. Average: 9 1. Grading Policy: +2 if a clear premise is stated. +6 if each round in the FloodSet procedure in the problem is stated clearly +2 if how the wrong decision is made is shown. 2. General Comments: Most people use a simple and correct example: suppose no process is faulty but one process with a different value from others is too slow to let others know its value in f+2 rounds, thus a wrong decision is made. Some people define the behavior of GlobSynch that GlobSynch ignores the round-r messages after receiving n-f messages in that round to show its incorrectness. The common errors include: 1. Some people consider a situation that the faulty process sends its value to a portion of processes while the others don’t get the value. But it is impossible under GlobSynch. 2. When the decision is made is not stated clearly: it should be after f+1 round, not after f rounds. 3. Some consider Byzantine failure in FloodSet algorithm. FloodSet is for stop failure only. HW 4 Part a Question 5 ------------------------------------------------- 0. Average: 7.3 10 points: complete reasoning given about the general case 9 points: minor mistakes in reasoning about the general case 8 points: stated the general case but lacked proper reasoning 7 points: solved the problem for limited cases e.g. thinking only with j0 and j1, or covered the general cases of the problem but no proper reasoning given. 6 points: incorrect proof for limited cases 2 points: problem restatement only or complete misunderstanding of the problem 2. General Comments It was fairly simple to prove once you came up with the general idea about the problem. Many people did a very good job of proving it formally. Anyone who covered the general cases informally and stated why phi and events between pi and phi that phi depends on can reordered (or in the same way, pi and events between pi and phi that depend on pi) also got full credit. Some people dealt with the problem only about j0 and j1, and some people simplified the problem too much and proved it only with three or four events in specific order. Some solutions tried contradiction but all of them contained fatal logical fallacies of assuming the statement to be proved as true. HW 4 Part a Question 6 ------------------------------------------------- 0. Average: 9.9 1. Grading Policy: -1 : an execution that doesn't work, unclear explanation, proof with logical defects 2. General Comments Most people described an execution where mutual exclusion condition does not hold at the end of the execution. If the execution is correct, they got full credit. Some people didn't give enough description about how mutual exclusion condition is broken. Some people tried to prove that it is impossible for two processes to be in critical region at the same time, but failed to present an integral proof. HW 4 Part b Question 1 ------------------------------------------------- 0. AVERAGE: 7.5 1. Grading Policy: Those who didn't describe an actual execution, but otherwise argued correctly, got 3 pts off. Those who didn't describe the execution and made some incorrect arguments got 6 pts off. Those who claimed PetersonNP does give bdd bypass got 1 pt. 2. General Comments: Most got this right. Some didn't know the correct definition for bdd bypass, which is that we start counting steps after someone enters the trying region and does a local step. Those claiming PetersonNP gives bdd bypass thought the system was operating synchronously. HW 4 Part b Question 2 ------------------------------------------------- 0. AVERAGE: 9.4 1. Grading Policy: 9 points for describing general situation 1 showing that the situation/execution is low-level fair 2. General Comments: Everyone basically got this question correct. Points taken off are more representative of not having a complete solution written down. HW 4 Part b Question 3 ------------------------------------------------- 0. Average = 6.8 1. Grading Policy: 7 Correct analysis 3 Correct solution -3 for exponential orders -2 for orders such as O(n^3.l) or O(n^2.l) whose proof is incorrect. -1 for orders such as O(n^5.l) whose proof is correct. 2. General Comments: The general strategy was considering of the highest level in which there is some processes and say after O(nl) time some of the processes progress one level and then continue to find the bound O(n^4l+n^2c). The solutions which constructed exponential examples were rare, however some solutions tried to prove bound O(n^3l) instead of O(n^4l), but I could not find any correct answer among them. Also solutions with polynomial bound more than O(n^4l) such as O(n^5l) were very rare. HW 4 Part b Question 4 ------------------------------------------------- 0. Average = 8.1 1. Grading Policy: 1. Modification Algorithm : 4 I was just expecting the basic idea here, a pseudo-code was appreciated, but I have given full credits even otherwise. 2. Proof of Correctness: a. Well-formedness 0.5 b. k-exclusion 2 c. Progress 1.5 Here I was expecting not-lengthy but convincing proofs. 3. Stating the high level fairness conditions : 2 a. Lock-out freedom b. Time Bound c. No Bounded Bypass Here I gave credits just for stating the conditions. General Comments: ----------------- Most got the basic algorithm correctly, however, and I empathize, because of the various details to be proved, missed a few points. Quite a few people missed well-formednesss and progress in Correctness. Also many did not mention high level fairness, some just mentioned fair executions in its place. A few students changed the algorithm so much that it did not seem Peterson's Algorithm at all! I had to deduct some points there, to be fair to other students who had given Modified Peterson's Algorithm. I have given full credits for all modifications which seem to be variants of Peterson's Algorithm. I would request people to be a bit more legible in their handwritten solution, however, no marks have been deducted from the answers of those who chose to tax my eyes. I have given specific explanations on every sheet for every deduction however small. HW 4 Part b Question 5 ------------------------------------------------- 0. Average = 8.8 1. Grading Policy: part a) 7. Time analysis from L region to M region 4. Time analysis from M region to C region: 3. part b) 3. 2. General Comments: In the algorithm of the text book, the order of checking processes in the loops is not mentioned. If the order was increasing (i.e. 1 to i-1), then there exists an example in which it takes O(n^2l) and the upper bound is O(n^2l) as well. If the order was decreasing (i.e. i-1 to 1) in the first two loops, it can be shown that the upper bound is O(nl) and not O(n^2l). Almost every one assumed increasing order. HW 4 Part b Question 6 ------------------------------------------------- 0. Average = 9.2 1. Grading Policy: Most got this right. Some made small mistakes in their proof, and received 1 or 2 pts off. Other made more serious errors, like saying modified Bakery is wrong because it doesn't guarantee bounded bypass. Depending on how correct their argument was, they got some credit. Some just claimed Bakery was wrong without saying why, and got 1 pt. 2. General Comments: Most said 'assume there's a proc with num = b-1', without saying how this would happen. But since so many did this, I didn't take off pts.