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)