Graders report for HW 2 HW 2 Part a Question 1 ------------------------------------------------- 0. Average: 8.8 1. Grading Policy: 7 Algorithm 3 general solution for f faulty nodes 2. General comments: The general strategy of a value only propagating one node per round because of a failure seemed to be the most popular. While most people showed how this strategy creates an inconsistency, some people only explained for the case of a specific number of faults. The solution called for a general strategy for f faults. HW 2 Part a Question 2 ------------------------------------------------- 0. Average: 8 1. Grading Policy: 7 Correct implementation of the algorithm 3 Agreement argument 1/3 some sort of correctness argument 3/3 agreement shown 2. General comments: The algorithm was straight forward and most people did not have a problem following the steps. There seemed to be a misunderstanding of the question, which called for random assigments of inputs to the different processes. Some people went through a validity argument by making all the non-faulty processes start with the same value. The question, instead, asked for an agreement argument by showing how even on random inputs, all processes decide on the same value. HW 2 Part a Question 3 ------------------------------------------------- 0. Average: 8.1 1. Grading Policy: 7 : correct method -2 : vagueness 3 : justify correctness 2. General comments: For the students with the right idea (have two processes connected by one edge simulate two subgraphs in each process), the solutions were mostly detailed and straightforward (answers were usually "each process simulate two groups of arbitrary size", "one process simulates one, one process simulates the rest", and "each process simulates (n/2) processes"). However, almost a fifth of the students attempted to prove the contradiction by using the "remove messages" method used in proving Theorem 5.1, and leaving only messages between two processes i and j. Though this can be shown to work, in most cases students failed to present a validity arguement that is required in this case. Note that unlike the trivial graph proof, in this case (since not all messages are beeing removed) removing messages can have an effect on future messages sent by i and j. In addition (at list intuitively), since many masseges are removed, i and j may decide 0 even if both start with 1. Thus, you had to show that this cannot not happen in order to prove the validity requirement. HW 2 Part a Question 4 ------------------------------------------------- 0. Average: 8.7 1. Grading Policy: 5: Algorithm -2: failure to set value if only n-2f or more messages -2: wrong bounds 5: Justify Correctness -2: wrong bounds -2: justify n-2f 5 for algorithm 2. General Comments: The answers were fairly consistent, since it was derived from a algorithm in the text. However, some people have very loose bounds in their algorithms and correctness proofs, and some people do not set v/y/z to be the majority of the values whenever it's larger than >=(n-2f) in round 1 (only setting v/y/z when >=(n-f)). Not forcing such a requirement will not guarantee the processes to agree on the same value. HW 2 Part a Question 5 ------------------------------------------------- 0. Average: 8.3 1. Grading Policy: Part (a) +4 -- develop (approximately) correct recursion or counting argument +2 - explain how the recursion is developed +1 -- solve to \Omega((2n)^f) Part (b) +2 -- note necessary changes in recursion or counting argument +1 -- remove O(2^f) factor 2. General Comments: Virtually no two people produced the _same_ exact solution in part (a)... Partially this is because different people used slightly different assumptions to solve the problem without completely specifying those assumptions. In part (b), the arguments were typically correct, but a common error was to claim that the chain length would only be halved, and not mention the 2^f reduction factor. HW 2 Part a Question 6 ------------------------------------------------- 0. Average: 8.3 1. Grading Policy: 5 points for the algorithm+description 2 points for correctness 3 points for proper time bound 2. General Comments: There were two main solutions - comparing the number of failed nodes vs round number, and requiring the same set of messages for two consecutive rounds. Only a very few solutions didn't contain a working algorithm - most of the non-working ones confused the W sets unchanging with number of messages received unchanging. HW 2 Part b Question 1 ------------------------------------------------- 0. AVERAGE: 8.8 1. Grading Policy: part a: 6 points part b: 4 points 2. General Comments: Not everyone remembered to do part b. HW 2 Part b Question 3 ------------------------------------------------- 0. AVERAGE: 9.6 1. Grading Policy: 2.5 for each part, rounded up. 2. General Comments: Some students considered UID's for part d. HW 2 Part b Question 4 ------------------------------------------------- 0. Average = 7 1. Grading Policy: here was a lot of variation on part A, which was worth 7 points total. In general, the right idea of using multiple Byzantine agreements was worth 4 points. Two points if they handled the synchronization right. One additional point if the proof was clear, convincing, and (most importantly) seemed to cover the details most left out. Part B was worth 3 points. A correct solution was worth 3. Those who didn't get full credit were usually way out in left field, but a few got 1 or 2 points if they were on the right track. 2. Comments Almost no-one handled the synchronization of processes correctly. Many algorithms specified that an externally woken up process "announces" itself, and a Byzantine Agreement algorithm runs next. But if a faulty process announces itself to a subset of all processes, the Byzantine Agreement algorithm will begin on some nodes and not on others. In part B, most students related the BFS to BA, which leads to a contradiction. Some students tried to show that their part A algorithm didn't work as proof that no algorithm worked, however, and received no credit. HW 2 Part b Question 5 ------------------------------------------------- 0. Average = 8.86 1. Grading Policy -5 for only showing case r=3. -3,-4 if was not clear how the proof held for r>3 / Arguments made were not clear -2 Analysis was mostly right but some errors did exist -1 Minor errors 2. Comments Most of the students used induction solve this problem. The base case was Lemma 7.22. It was assumed that the lemma was true till after round 3k. It was then not difficult to extend the lemma to after round 3k+3. Another approach used was to show the lemma was true for an arbitary round r=3k (k= 1,2...). Many students got full credit for this problem. A few students showed the problem only for the case after r=3. They lost 5 points since this case was mostly covered in the textbook and the problem specifically required lemma 7.22 to be shown for all r. The proof for r>3 was similar but not identical to the case r=3.