PROBLEM 1: CANCELLED -------------------------------------------------------------------------- PROBLEM 2. AVERAGE = 9.875 1. Grading Policy: 5 pts for doing the problem 3 pts for atomicity 1 pt for termination 1 pt for well-formedness 2. General Comments: Most people got this problem right. A few lost points because they forgot to mention well-formedness. Very few thought termination didn't hold; even fewer thought well-formedness didn't hold. A select few realized that the cost of losing property 3 was the time-bound. The one person who got everything right, mentioned the loss of the time-bound, and typed the solution got a 10+. -------------------------------------------------------------------------- PROBLEM 3 AVERAGE = 9.25641 1. Grading Policy: Part a: 4 Part b: 1. logical time construction: 2 2. proof of the 4 properties of logical time: 2 3. proof of the weakness: 2 2. General Comments: this problem was kind of straightforward and formal proof was not required. most of the students got full points. i took some points off when they failed to show the above 3 points. -------------------------------------------------------------------------- PROBLEM 4 AVERAGE = 9.4 1. Grading Policy: essentially everyone got it right, for 10 pts. 2. General Comments: i looked for 3 things: a) state that DS and ABA solve two different problems b) ABA only deals with one msg on predetermined tree while DS deals with multiple messages which it has no idea about beforehand. c) underlying algorithm affects tree configurations in DS; no such problem in ABA. basically any sort of combination of b or c would get full credit, as they both imply a which was partial credit. -------------------------------------------------------------------------- PROBLEM 5 AVERAGE = 9.5 Grading Policy: Everyone had the basics the algorithm. I took off a few points for: -1 Providing a local implementation of the algorithm, i.e., everyone forwards their waiting-for values to a leader, which performs local analysis on the sets. The problem requested a distributed algorithm (in contrast to the local DFS algorithm provided on p. 636). -.5 Missing/incorrect complexity analysis. -.5 Failure to mention applicability to deadlock detection. -.5 Minor problems with the algorithm, e.g., infinite loops. Histogram: 7.5: 1 8: 2 8.5: 1 9: 2 9.5: 20 10: 11 10+: 4 Mean: 9.512 Median: 9.5 -------------------------------------------------------------------------- PROBLEM 6 AVERAGE = 8.5 People gave a few different solutions to this problem. Type 1: Exponential increase in low-level messages per high level message ( (k+1)^n ) Mostly done very well. Only problem was that many people didn't show liveness/termination (based on the fact the channel is lossless). I was not picky with k vs. k+1 vs. k+2. -2 No proof -1 Only sending one ack instead of (k+1)^n (or no acks) -0.5 No liveness Type 2: Implement a lossy, reordering, non-duplicating channel and use it for Layer 1 in Probe. Only problem with these is that some people did not show that loss was limited (i.e., that some messages would eventually get through). I deducted 1 in this case. Type 3: Alterations to the value of old for Probe. Again, almost all correct. Only problems can from forgetting that the probe messages can be duplicated as well, resulting in old = pending * (k+1) rather than (k+1)^2. I deducted 1 in that case. A few misc algorithms that were fatally flawed, either because they were lossy or allowed reordering. They were awarded marks in the 2 - 4 range. -------------------------------------------------------------------------- PROBLEM 7 AVERAGE = 9.65, median = 10, mode = 10 7 points: correct answer (yes/no) 3 points: argument, presentation, effort a plus was awarded for a thorough argument Most people got this problem correct. Most people realized that the properties of the pending variable, after the modification, will be sufficient for the proof to go through. There was little room for creative license in this problem.