General comments and suggestions: - Some proofs were not formal enough. You have to try to maintain the same level of formality that is presented in the book, unless the question requires only a "convincing argument" or a "proof sketch". - However, formal does not imply lengthy. Be as concise as you can, without leaving room for ambiguity. - Different questions are assigned to different graders, therefore: (1) Write each problem on a separate page, and write your name on that page. (2) Do not refer to your answer to another problem, graders do not have access to all problems. +-------------------+ | Problem Set 1 (a) | +-------------------+ Problem 1 ========= part a) +5 points for having UIDS decreasing in the direction of communication part b) +5 points for having UIDS increasing in the direction of communication -2 points if only a specific example was given, instead of a general equation in terms of n Problem 2 ========= (a) 5pts 1 pt - What was the problem with the modification 1 pt - What is the worst case 1 pt - Correct Math 2 pts - Setup summation properly (b) 5pts 2 pts - How to fix the problem 3 pts - Arguement for how it fixes it Problem 3 ========= Problem 3 of Part A asks: "Is this problem solvable or unsolvable? Why?" Therefore, a perfectly correct answer could read: "No, because symmetry cannot be broken." The question did not ask for a proof. Additionally, the question asked whether the problem was solvable for all n, meaning that a proof of impossibility for n=2 is a proof by counterexample that the problem is unsolvable. In our discussion session, however, Prof. Lynch made it clear that she was looking for a proof that it is unsolvable for any n, and that proof needed to involve symmetry and neighborhoods and so on. My grading rubric reflects her expectations, not my own interpretation of the problem. Breakdown: Total 10 k-neighborhoods/symmetry +2 proof quality +5 works for all n +1 unsolvable +2 Problem 4 ========= In general: +2 points for the big idea that the number of active processes were cut in half at each phase +2 points for the big idea that a process could take on the UID of another process +3 points for a correct algorithm with reasonable correctness argument +1 point if correct algoirhtm with no argument +3 points for correct and complete argument about complexity -1 point for not explaining why only 2n messages are sent per round There was more than one way to solve this problem, and this scale was for the PetersonLeader way. The other valid solutions follow a similar scale. If you used the PetersonLeader algorithm from the book (or from a paper) as the basis for your solution, you should have cited it appropriately, but no points were taken off for failure to do so. Problem 5 ========= 7 pts for part a + 3 pts for part b For a: 0 - lower bound makes no sense 3 - Omega(n) rounds 3 - Tried different approach, didn't work 5 - Proof of Omega(n) rounds not rigorous (e.g., claiming you need to "break symmetry") 7 - Show at least Omega(n) rounds; use proof from book to show Omega(n log n) For b: -1 : Forgot to send estimate around the ring Overall 6 - If assume leader known -1 : Use omega instead of Omega -1 : Proof of Omega(n) not shown +-------------------+ | Problem Set 1 (b) | +-------------------+ Problem 1 ========= Pseudocode 3 Proof 7 - base case +1 - induction +4 - simulation setup +2 Problem 2 ========= For part a) the essential points were: 1. The algorithm is based on the SynchBFS algorithm 2. The prunning of the tree is done by doing a convergecast. Specifically it was important to understand that: + Nodes have to be initialized so that if they already have adjacent hosts they will not be pruned. Of course this can also be done later in the procedure before the node is prunned. +Convergacast works by starting at the leaves and they notify their parents whether they should be prunned or not +A node only notifies its parent after it has received all the messages from its children. For parts b) and c) I was looking for a convincing argument that showed that: 1. The network formed was still a tree. That is, no cycles were introduced by the modifications made to SynchBFS. 2. A node was in the tree if and only if it had an adjacent host in the multicast group or another host in its subtree had an adjacent host in the multicast group. Some people only showed one direction. 3. The algorithm terminates and r0 is notified when this happen. Forgetting to show this, was by far the most common mistake. It was of course valid to split the above conditions into several more. Problem 3 ========= 10 - Correct Answer 7 - Didn't generalize to arbitrary n 3 - Didn't work at all -1 for additional flaws Problem 4 ========= Psuedocode: +1: a description (in words) exists +1: psuedocode exists +1: The description and psuedocode are clear and correct Time Analysis: +1: analysis is there and correct (O(n)) +1: for a correct explanation of why this is the time bound +1: analysis is clear and easily understandable (ie, i didn't have to spend significant time reading and rereading and hunting to figure out what the student meant.) Proof of Correctness: +1: proof exists (ie, student remembered to prove this) +1: for a correct explanation of why the algorithm works +1: analysis is clear and easily understandable (ie, i didn't have to spend significant time reading and rereading and hunting to figure out what the student meant.) Right Idea: +1: Student understood what was expected and presented the "right" idea. Problem 5 ========= 3 pts - right answer 3 pts - correct inductive arguement 2 pts - Change original input properly 1 pt - Bounding r in the proof (if they went with the reduction method that was worth 3 pts for a reasonable arguement that failed)