HW4: PROBLEM 1: Average: 6.32 1. Grading Policy: My grading roughly followed this scheme: 3 points for correct algorithm 2 points for correct mutual exclusion 2 points for correct progress ~3 points for something on the higher level guarantees I broke from the scheme a bit for low scores...The problem is that if you miss the fairness part of your algorithm, then you can [and most people did in this case] copy the proofs right out of the book/refer to the book. Many people had the wrong idea for the progress proof. 2. General Comments: Many people tried to use proofs from books. There are some technical details they needed to address that they didn't. IE...Lemma 10.5.3 isn't true for k-exclusion algorithm as stated in book. [The part of the lemma regarding the S set depends on how people defined their S sets. Some people carefully defined S to keep this part of the lemma true.] PROBLEM 2: Average: 8.6 1. Grading Policy: I divided the points for this question as follows: 3 - For getting the main idea of the question (i.e. that a process can delay another process after that process had finished the first loop) 1 - Proving the time it takes to finish the first loop 2 - Proving the time it takes to finish the second loop 1 - Proving the time it takes from M to C 3- The lower bound example 2. General Comments: Most of the students got correctly the main point of the question (that a process can delay another process after that process had finished the first loop). If a student didn't look at that possibility, and just looked at the time from when a single process enters T until it enters C (without taking into account possible interference by other processes), he lost most of the points for this question. Two other problems that appeared in solutions where: 1) Some students wrote that it takes time of O(nl) to finish the first two loops, while it takes an addition (n^2l) to finish the third one. This is not true. The time from when the first process enters M until some process enters C is just 2nl at the most (see the solutions) - and the really slow loop is the second one. 2) Some students didn't prove correctly the time it takes to finish the third loop. Its not enough to say that when a process i enters M, all processes j>i will set their flag to zero in nl time, because it could be that a process j>i is in his second loop and already passed i in that loop, so he will enter M too (after i). Now, another process k>j will do the same thing and enter M as well. So you must say something about the time this group of processes (j>i) stabilizes, and no more such processes can enter M. PROBLEM 3: Average: 8.846153846 In general, most students got the right approach. Everyone stated that the modified algorithm fails, and over 90 percent of the students stated that mutual exclusion was violated. The most common problem in students' solutions is failing to show that number(i) can actually get accumulated to b. I only deducted 1 point for this problem. There are a few serious problems. For example, some counterexamples are not stated clearly and tend to be "hand-waved". I deducted some points according to how clearly the counterexample is constructed and explained. PROBLEM 5: Average: 9.18 Grading Scheme: Part a counts for 8 points, while part b (general case time analysis) counts for 2 points. For part a, most people saw that the original algorithm still works for an odd-sized ring, and hence received most of the marks. The ideal answer is 4c+23l. For part b, as long as you see that the time bound if O(ck+lk), where k is k is the length of the longest waiting chain, then you get a full mark. Common Mistakes for part a: 1) 1 point is taken off if one did not realize that the upperbound of S is now different for each process, and instead of simply bounding T by T <= C + 2l + 2S, a tighter bound would be T <= C + 2l + S + Sn, where S is the original S in the book, and Sn <= 2c+13l. A lot of people simply used 2c+13l for S, resulting with a looser upperbound for T : T<=5c+26l, instead of the tighter bound T<=4c+23l. 2) 1 point is taken off if no detailed time analysis was given and the resulting time-bound is way too loose. No points were taken off if there were any small miscaculations in the coefficient of l. 3) 1 point is taken off if the time-bound is way too loose. Common Mistakes for part b: 1) A number of people forgot to do this part. 2 points are taken off in this case. PROBLEM 6: Average: 9.26 Grading Scheme: 1 pt for YES to part(a) 1-failure termination 1 pt for YES to part(b) 1-failure termination 5 pts for correct algorithm for part(a) and (b) 3 pts for understanding the problem and attempting to solve -1 pt for incomplete or unclear parts 2. General Comments: Most people either used PetersonNP algorithm or simulated RMW using PetersonNP. In any case, all correct solutions implemented Mutual Exclusion. Few stated that there is no algorithm possible for this problem. Hopefully the sample solution will convince them that it is possible. Initially, points were taken off for not specifying why the algorithm guarantees the wait-free and 1-failure termination; however, these points were given back since the sample solution did not specify this, problem does not ask for this proof, and it is obvious from the description of the algorithm. PROBLEM 7: Average: 9.095 1. Grading Policy: 8 points for a working counter-example. (ie one that does not exhibit atomicity) 1 point for showing that the example given is actually a valid execution (ie explain when the reads occur and what values are read etc.) 1 point for explaining why it doesn't show atomicity (ie the value is never the one reported, or no serialization corresponds to the output) + Since the problem was fairly simple, 10+ was awarded on the basis of brevity. 2. General Comments: The problem was fairly easy considering that the solution was easily drawn from the examples presented in class. Everyone presented a correct execution. The only problem anyone had was in explicitly explaining the two key points of the counterexample (that it is valid, and that there is no serial explanation). Since the explanation was very simple (eg "the sum was never the value output"), and the problem did not ask for a rigorous proof, these omissions were only slightly penalized.