Graders report for HW 5 HW 5 Part a Question 1 ------------------------------------------------- 0. Average: 9.5 1. Grading Policy: Full credit for working algorithm, -1 for minor specific problems, -2 for two minor specific problems or a less minor specific problem. 2. General Comments: Just about everyone interpreted differently whether the execution sequence needs to be explicitly maintained and whether the clock is maintained as a separate task or given as an input. Since these do not dramatically affect the simple algorithm, I gave full credit for any reasonable interpretation. HW 5 Part a Question 2 ------------------------------------------------- 0. Average: 9.3 1. Grading Policy: -1 if did not explain in sufficient detail how to modify the proof of Lemma 12.3 -5 if did not prove lemma 12.3 correctly -1 if did not (correctly) justify why the proof of Lemma 12.7 still applies -1 for other minor mistakes 2. General comments: Most students solved this problem by noting that the proof of the theorem in question does not depend on the validity condition, except for Lemma 12.3. One point was taken off if the solution merely stated that the proof of Lemma 12.3 can be modified using the given input-first executions alpha0 and alpha1 but did not further explain how this is done. At the minimum, the solution had to state that we can construct a chain of executions from alpha0 to alpha1, changing one input at a time, and reach the contradiction in the same way as in the original proof. HW 5 Part a Question 3 ------------------------------------------------- 0. Average: 8.9 1. Grading Policy: 7 points for algorithm (2 for LogicalTime, 3 for ReplicatedStateMachine, 2 for QueueME), 3 points for sketch of proof 2. General Comments: Most problems were caused by people not including one of the 3 algorithms that should have been combined, usually the QueueME, but some people managed not to include others. A lot of people forgot to have each process send an infinite number of dummy messages. HW 5 Part a Question 4 ------------------------------------------------- 0. Average: 8.6 1. Grading Policy: 8 points were given for modifying the algorithm(or not at all), showing the modification to be correct and giving a correct time bound. 5 points were given for a correct algorithm and proving the modification was correct. 3 points were given for the actual time bound. Most people proved correctness by explicitly calculating a time bound. The best possible result was 4c+21l with most people giving 4c+23l. 1 point was taken off for bounds that had a constant greater than 4 on c provided a valid argument was given that it was an upper bound on the time. 2 points were given for the generalization to arbitrary right-left algorithms. Some people generalized by talking about the worse possible "right-left" algorithm (one that has only one left and n-1 right processes). This results in a bound of O(n(c+l)). Others observed that regardless of the size of the ring, all that matters is the longest chain of processes of the same type. In this case, a bound should be gotten of O(k(c+l)) where k is the length of the longest chain. Full credit could be gotten with either of these interpretations of the problem. 1 point was taken off for not at least giving an order bound in terms of n(or k), c and l. 2. General Comments: The easy solution to this problem is to observe that no changes need to be made and just deal with the two adjacent nodes that then have the same handedness. A few people tried to make more complicated modifications, but people who did this tended to miss some of the technicalities their modifications introduced. Many people came up with a bound of 5c + 24l. This is a correct bound but a slightly more careful analysis y ields 4c+23l or 4c+21l. Many people skipped the part about general right-left algorithms, and this is where most of the points were missed. As stated above there were two reasonable interpretations for the last part of this problem. Some people calculated a bound in terms of both the longest sequence of left nodes and the longest sequence of right nodes. This proved to be more complicated but still yielded the correct order dependence. HW 5 Part a Question 5 ------------------------------------------------- 0. Average: 8.8 1. Grading Policy: Half credit for a clear proof that happens to be wrong regarding why this won't work. An additional point off for an algorithm that fails. 2. General Comments Either they got it all correct, or they missed something major, like assuming that it was impossible because of Theorem 12.8. HW 5 Part b Question 1 ------------------------------------------------- 0. AVERAGE: 9.5 1. Grading Policy: Correct counter-example: 8 Explanation: 2 2. General Comments: HW 5 Part b Question 2 ------------------------------------------------- 0. AVERAGE: 9.4 1. Grading Policy: Correct counter-example: 8 Explanation: 2 2. General Comments: The general strategy to solve this problem was to come up with an execution in which the system violates atomicity. Many people did not come up with a correct counter-example. For example, an execution with the trace: WRITE(v1)_1, ACK_1, WRITE(v2)_2, ACK_2, READ_3, WRITE(v3)_2, ACK_2, v2_3 in which WRITE(v3)'s internal 'write' operation completes in between the internal 'read' operations of READ, is valid since we can asssign serialization point to READ_3 before the serialization point of WRITE(v3)_2. HW 5 Part b Question 3 ------------------------------------------------- 0. Average = 8.7 1. Grading Policy: Modifying the algorithm. It was sufficient to assert identical behavior as for the UnboundedSnap algorithm save for the consistency checks. (3 points) Proof. The scoring for the proofs is subtractive: various types of mistakes are penalized. These mistakes are eneumerated below (7 points) Simulation relation. No simulation relation exists (see below). However, if arguments were made to ameliorate the problem with updates to .val (see below) only 1 point was deducted and if none were, 2 points were deducted. Other methods. The problem with updates which do not change the value of any .val fields is not addressed: -2 points. 2. General Comments: Many tried to show a simulation relation between the two types of UnboundedSnap algorithm. No such relation exists as traces(UnboundedSnapNoToggle) is not contained in traces(UnboundedSnap). Consider the following execution fragment which makes sense for either algorithm. -------- update(v)_i starts and completes. update(v)_i begins Processor i completes all processing for this save writing the new values to x(i). snap_j begins Processor j completes all processing through the end of the first read of the first consistency check. i writes the new values to x(i) and issues ack_i Processor j now performs the second read of the first consistency check. ------- As in the execution from the book, all comm(j) fields are unchanged between the two reads for j. For UnboundedSnap, the x(i).toggle field did change, so the next external action of proc j will involve reading the .comm(j) fields in preparation for another consistency check. For UnboundedSnapNoToggle, we have all .val fields unchanged, so the next external action for j is returning the values found to U_j. Thus there are traces of UnboundedSnapNoToggle which are not in traces(UnboundedSnap). Moreover, if an update occured immediately after the above steps, the snap in UnboundedSnap might eventually return a different vector than that from UnboundedSnapNoToggle. The other method of solving this was to argue that if UnboundedSnapNoToggle found two reads consistent then no .val field changed between them so the proof in the text works for this algorithm as well. These produced the most succint proofs. HW 5 Part b Question 4 ------------------------------------------------- 0. Average = 9.4 1. Grading Policy: took off 1 point for not simplifying the algorithm by eliminating the choosing variable. took off 1 point for arguing, rather than "proving" mutual exclusion took off 1 point for proving by saying, "this is pretty much the same as the proof in the book", or some other variation took off 1 point for not clearly writing pseudo-code for the algorithm, though I gave credit for a particularly good explanation General Comments: ----------------- This was straightforward, so most everyone got it correct. Most common problems: did not simplify by eliminating the choosing variable did not prove ME, rather wrote, "the same as the proof in the book" HW 5 Part b Question 5 ------------------------------------------------- 0. Average = 8.4 1. Grading Policy: Statement of theorem. (2 points) If the theorem was restricted solely to snapshots implemented on read/write shared memory, one point was deducted. If there was no clear statement but it was stated in a sentence in the discussion that "There is no algorithm using atomic snapshot shared variables that solves 1-failure agreement" or something very similar, full points were awarded. Proofs: (8 points) By contradiction: The wait-free (or at least 1-failure termination) property of the read/write implementation was not mentioned: -2 points. It was assumed that all atomic snapshot objects use only read/write variables in their implementation. The book only shows that they can be so implemented. -2 points Following the proofs of 12.1: Problems were individual and usually fairly minor. The reasons for point deductions are given on the individual homeworks. 2. General Comments: There were two major approaches to this problem: Proof by contradiction: This was a bit more popular. Snapshot atomic objects may be implemented (wait-free) using read/write shared variables as per section 13. This gives a contradiction by theorem 12.8. Types of problems encountered: many did not address the wait-free propert of the simulations in 13.4. At least 1-failure termination is required for any simulation (implementation) if we want 1-failure termination for the whole algorithm. Modification of proofs leading to 12.8: the proofs leading up to (and including) 12.8 could be adapted almost without modification to apply to snapshot shared variables (replace reads with updates and writes with snaps). Snapshot variables are in some sense partioned read/write variables, where certain portions can only be updated by a particular port (or process). The way it was defined, a snapshot variable is a shared memory variable with certain read-type and write-type operations avaiable to it. The problems encountered with this type of proof were minimal and mostly unique to each pset.