Graders report for HW 3 HW 3 Part a Question 1 ------------------------------------------------- 0. Average: 8.9 1. Grading Policy: a) 6 pts +2 for reasonable progress +2 for exhibiting all behaviors +2 for working within constraints b) 4 pts +1 per trace/execution HW 3 Part a Question 2 ------------------------------------------------- 0. Average: 9.8 1. Grading Policy: +8 for right idea +2 for right answer HW 3 Part a Question 3 ------------------------------------------------- 0. Average: 8.1 1. Grading Policy: For solutions that were mostly correct except for the common problems that I describe in part 2, I took off 2 points. Some solutions also had the general idea but were, in my opinion, underspecified. For example, some solutions would claim that something could be done but didn't specify how when the details were important (devil's in the details). I took off 1 to 2 points here depending on how serious the omission was. Finally, some of you mixed tasks and actions and used them interexchangeably. A trace is actually composed of a sequence of actions, not tasks. So, in some cases, solutions would have had the wrong naming. I took a point off here. 2. General comments: The general strategy encountered in solutions was to create in B some form of a fair scheduler for the Tasks of A. For example, many students proposed a counter variable in B that would increment mod |tasks(A)| and reference a particular Task in A. An action from that Task would be enabled if it were enabled in A. This would be a simple round-robin scheduler. This example also illustrates one of the common mistakes encountered, that being using a round-robin scheduler. The problem is that |tasks(A)| need not be finite, only countable. Hence, a round-robin scheduler will not satisfy fairness because we can construct a fair execution in A that is not in B. Another common problem I encountered was to have B simulate A without any form of scheduling. While this satisfied the fairtrace inclusion condition for finiite traces, it fails for infinite traces. HW 3 Part a Question 4 ------------------------------------------------- 0. Average: 6.8 1. Grading Policy: +2: using induction or other correct methods +2: base case in the induction proof +4: inductive step in the induction proof +2: clarity in the proof 2. General Comments: Most people solved problem by standard induction method and few by contradiction, which is also correct. The induction step needs to be clearer. Some people "argued" in the absence of logic, other than proved the correctness, and received no credit. There are some fundamental errors, for instance, some people think trace(C) is a subset of trace(CxD), which should be the contrary, i.e., the project on C of trace(CxD) is a subset of trace(C). Other errors include that some people directly concluded ext(A') is a subset of ext(A). This is only correct in the context of B. HW 3 Part a Question 5 ------------------------------------------------- 0. Average: 8.8 1. Grading Policy: 10 points - anyone who mentioned splitting the ring into pieces with sizes that were powers of 2, and gave as a lower bound the summation o f the number of messages for each of the pieces. 8 points - anyone who mentioned splitting the ring into pieces with sizes that were powers of 2, but did not mention the summation of the number of messages for the pieces as a bound. 6 points - anyone who mentioned splitting the ring into pieces, but did not mention that all of the pieces had sizes that were powers of two. 2. General Comments: A lot of people came up with the desired summation but then attempted to come up with a closed form expression that approximated the summation. However, these closed form expressions were all smaller than the actual summation, and hence a WORSE lower bound. Many people also suggested splitting the ring into one piece that had a size that was a power of two, and then one "remainder" piece - although this is sufficient for finding an asymptotic bound, it does not obtain the desired best lower bound. HW 3 Part a Question 6 ------------------------------------------------- 0. Average: 8.6 1. Grading Policy: Solution aspect and points awarded: 1. Correct Algorithm - 4 Points Doing Garbage Collection after checking reported = true. 2. Ensuring that the neighbors won't be hanging after a process garbage collects - 2 points. 3. Verifying that send queue is empty - 1 point 4. Correctness Proof - 2 Points 5. Complexity Analysis - 1 point. 2. General Comments: With respect to post-garbage-collection state, there were two different approaches: 1. Processes exit 2. Processes continue to run, but the processes return to the state before the algorithm started. Both these approaches are considered right. It is important to understand that the processes cannot simply garbage collect. That is, although the precondition (reported = true) for garbage collection might be true, the send queues may not be empty. So, it is absolutely necessary to make sure that the queues are empty, if the processes exit or send queues are not reset. Most people understood that simply garbage collecting is not correct. They have taken some steps to ensure that the other processes are not left hanging waiting for a reply from a stoppeed process. Realizing this is important and so people were given credit (2 points) for this. More importantly, send queue must be empty before garbage collecting. 1 point was deducted, if this is not explicitly stated. Some answered that just modifying the algorithm to garbage collect as soon as the precondition was satisfied would work. Obviously, this is incorrect and so 3 points were deducted. Surprisingly, some didn't provide the complexity analysis. HW 3 Part b Question 1 ------------------------------------------------- 0. AVERAGE: 8.7 1. Grading Policy: -1: if student used some form of inductive argument for component C' and some other component C'' at the same level, but failed to state what the base case was (2-length cycle MWOE). -1: Almost everyone failed to state that if some component gets absorbed by C, then C's MWOE won't change - no need to prove it since it is done in book, but students should have stated it to justify 2. General Comments: Most students resorted to the inductive argument: if the MWOE of C or C' goes to a component of higher level, then it is immediate; otherwise reason inductively. Two argued that C eventually had to connect to someone(since algorithm terminates) but couldn't connect to any component that didn't contain C'. HW 3 Part b Question 2 ------------------------------------------------- 0. AVERAGE: 8.1 1. Grading Policy: Defining the automaton was worth 5; defining the simulation and proving the assertion was also worth 5. Common problems: -1: not listing internal actions as being internal actions -1: not updating tag variables, such as last-tag-delivered -1: at least half the solutions didn't define tasks correctly. Many simply didn't define them; others didn't include internal actions in their tasks. "arbitrary" was an acceptable definition for the tasks, though only one student did it. -2: a reasonable amount of people used a test condition on the last-tag-delivered inside the transition corresponding to the output action receive(m), to remove a single duplicate message. These automata DON'T satisfy traces(D) is contained in traces(A), since output actions corresponding to the removal of a single duplicate message would appear in traces of traces(D) but not in traces of traces(A). -2: some defined a "simulation relation" based on actions of automata A, D and not on their states. -1: There were solutions which didn't need to remember the last tag delivered, by removing all duplicate messages on top of the queue in a receive(m) action. The functionality is correct, but it was required that the channel "remembered" the last tag delivered -those who didn't do it lost one point. 2. General Comments: The simulation relation was fairly easy to prove: some people did a really good job of proving it formally, but anyone who gave an invariant matching correponding states of the two automata and briefly stated why the states were the same after any action of D, got full credit. Some students specified messages to be duplicated only on the head or only on the tail of the queue. Some didn't need a special "duplicate" action because they inserted arbitrarily many copies of the message when it was first added. Some permitted a message to be duplicated only once per action. HW 3 Part b Question 3 ------------------------------------------------- 0. Average = 7.6 1. Grading Policy: Part a) 7 points - 2 points for correct upper bound, 1 point for base case, 4 points for inductive step. (Proving without induction would have to be pretty rigorous to achieve 5 points.) Part b) 3 points 2. General Comments The answers to part a were fairly consistent since the correct bound can be found in the textbook. Proof was done by induction on the number of levels. Some people had different bounds which they did not prove adequately. These got the most points taken off. Some people forgot the base case and they got 1 point taken off. Several students skipped part b, which is worth 3 points. The predominant answer is found in the solution sheet. Some answers specified properties of the execution which they wanted to achieve but did not say how the execution would actually proceed to get there. This got a deduction of 1 point. Some other answers had assumptions (such as a process searching for its local mwoe exhaustively, and not sequentially) that would then allow their particular execution to achieve the bound given in part a. As long as they state this, I did not take any points off.