----------------------------------------------------------------------------- PS 2, Problem 1 1. Grading Policy: Correct modification of the algorithm 3 points Correct termination argument 1 point Correct validity proof 3 points Correct agreement proof 3 points 2. General Comments: Most students had the correct solution, so there is no major problem in grading. A few students submitted only the algorithm without the proof, thus received only partial credit. ----------------------------------------------------------------------------- PS 2, Problem 2 Grading Policy: Correct conclusion: 3 Correct understanding of PolyByz procedure: 3 Correct contradiction: 4 ----------------------------------------------------------------------------- PS 2, Problem 3 Grading Scheme for Problem 3: Part a (6 points): Most students chose an algorithm that starts an EIGByz subroutine at every round, each process voting 1 if it had received a wakeup message and 0 otherwise. The main difficulty most people were faced with was synchronizing the different rounds of EIGByz that could be off by 1 step because some processes were dormant when some algorithms started. One solution was to start each EIGByz algorithm with a "rise and shine" message to everyone, so that all start simultaneously. The trick was to understand that if multiple instances of the EIGByz algorithm were run simultaneously starting at rounds r1, r2, etc, they would all arrive to agreements at rounds r1+f+1, r2+f+1, and so on. The synchronicity argument was then trivial, noticing that if rk is the round at which all non-faulty processes have finally received a wakeup message, the EIGByz algorithm that started at rk+1 (after the "rise and shine" message) would conclude at (rk+1)+f+1 with a fire initiative, and that it would be the first one to arrive at such an agreement. Grading: Algorithm idea.....: 2 points Algorithm details..: 2 points Proofs.............: 2 points Part b (4 points): There were two main groups of solutions, both of them correct. Solution 1: Reduce ByzAgreement to ByzFire. Reduction means that given an instance of the ByzAgreement problem, we can transform it into an instance of ByzFire. Instead of having to solve ByzAgreement, we can simply solve ByzFire. We have thus "reduced" the agreement problem into the 'simpler' ByzFire problem. Given an algorithm that solves ByzFire for n<=3f, we can now solve an instance of ByzAgreement for n<=3f. Hence the contradiction. Some students misunderstood the direction of the reduction. Others said the two problems were equivalent but didn't show either reduction. Some mistakenly said that "ByzFire is a special case of ByzAgreement" whereas it's the opposite. Another common mistake was to say that since our ByzFire was calling ByzAgreement, and ByzAgreement could not work for n<=3f, ByzFire could not work either. This is not a proof, since it only argues impossibility if we use a particular algorithm (with ByzAgreement as subroutine), as opposed to proving that there is no possible algorithm that can solve ByzFire. Solution 2: Rebuild the proof from the ground up Adapt proof in the book (p. 129 section 6.4). A common mistake was to only show it for n=3 and f=1, without the generalization part. Grading: Reduction idea............: 2 Constructing the Reduction: 2 OR: Base case n=3 and f=1.....: 2 Generalization............: 2 ----------------------------------------------------------------------------- PS 2, Problem 4 There was a wide variation in the algebraic answers given to this problem. However full points were given if the students demonstrated an understanding of the algorithm and came up with an answer that was in the ballpark. The exact solution was not required. 2-4 points were subtracted per part if the proof technique clearly was not understood. 1 point subtracted per important error in reasoning. 2 points were taken off the second part if the answer given was clearly way too short. 1 point was taken off the second part if no estimate was given of how much shorter the chain would be. Distribution of points Part A: 6 points Part B: 4 points ----------------------------------------------------------------------------- PS 2, Problem 5 1. Grading Policy: 9 for mostly correct soln, such as k + 1, due to rounding errors 8 mostly correct idea for proof. 7 general idea for proof 5 for mostly wrong answer. -2 incoherent example 2. General Comments: lots of people had rounding errors, but most did have the correct idea of proving the bound. Some had very loose bounds for the soln. ----------------------------------------------------------------------------- PS 2, Problem 6 1) Grading Policy: There were many careless mistakes in this problem, but marks were taken off systematically to be fair to students who spend time in being accurate in their coding. Furthermore, the book gave a very detailed explanation of the 3-phase commit protocol, and so more is expected of the code than otherwise. Marks are taken off for each of the following mistakes: 1) Failure to give some indication of the case when messages are not received by a process, or failure to include the null messages "received" in the cases. 2) Failure to send a message to yourself if you are the leader, or to initialize the vector in such a way that this is not required, or to do something of the same effect. 3) Not differentiating the 1st round where initial values are received from the 3k+1 round for k>1 where status messages are received. 4) Sending to the wrong process, i.e. someone that is not the leader, or not stating which process to send to, or calculating the wrong process to be the leader. 5) Forgetting a minor comparison or step. 6) Adding redundant steps to the algorithm thereby forming a modified algorithm that is not the 3-phase commit. For example, getting every process to broadcast their status at every round. 7) Not realizing that process 2 can broadcast decide(1) in round 5 whereas process 1 was unable to do so in round 2. 8) 2 or more parse errors (ambiguous statements). Eg. if (i=k) decide 1 and current-status=dec1 if (decision = unknown). This could mean: if (i=k) decide 1; end-if; if (decision = unknown) current-status=dec1, or it could mean: if (i=k && decision = unknown) decide 1; current-status=dec1; endif; 9) No clear termination at round=3n. 10) Not realizing that decision="ready" means that a process has not yet decided. 2 Conceptual Errors (eg. skipping "ready" all the time and going to "dec1") and Major Mistakes (eg. giving code for the 2 phase commit) were penalized more heavily. Notes: i) Each mistake from the above list will cost a point to be deducted. ii) For repeated errors, no additional marks were deducted. iii) Any algorithm that is mostly correct but made numerous careless mistakes (>5 unique errors) should get at least a 5 or above. i.e. No student fails for being careless. iv) The grade distribution was from 3-10. ----------------------------------------------------------------------------- PS 2, Problem 7 1. Grading Policy: 10 if it was correct, and nothing was wrong 10+ if I thought it was especially easy to understand 9 if it forgot to write down "task" but everything else was right. 7 if it was wrong, but probably because of they forgot something small. 6 if it was wrong. 5 if it was really wrong. 4 if they completely missed the problem altogether, but actually defined a real automaton (4 was the lowest) 2. General Comments: - half were about 10 or 10+. - most of the 6's were for the same error.(didn't account for getting a lot of sends before receives, and specified that there must be no M1 in order to send M2.) Basically, if they got 5-9: probably one of the following cases didn't work. m is in M1, n is in M2: - no n could be received without all the m's being received first. - getting four n's then an m, and having the m being received first. There were pretty much only two different solutions. One with one queue, and another with two queues(and some counting mechanism). There were 2 or 3 different ones(Val's is an example) which did something different. However, there were 5 that I just couldn't understand, and they're left ungraded, sorry. They're on top. ----------------------------------------------------------------------------- PS 2, Problem 8 About B's construction: (-1) If in the construction of B, one did not differentiate between locally controlled actions and input actions. e.g. mistake B's transition: for every s in states(A), pick any single (s,pi,s') from transitions of A. (-2) for those who constructed "hyper-states" for B, i.e. a state that corresponds to a set of different states in A, but failed to describe what to do with these hyperstates later. (i.e. what's the state transitions associated with these hyper-states etc) and did not relate the hyper-states with their arguments about fairtraces. i.e if a state is not enabled in a "hyperstate" in B, what could we say about the corresponding executions in A? Arguing that the fair traces of constructed B is a subset of fairtraces of A. (-2) for assuming that all executions of A and B are fair by definition (-2) for assuming that if traces(B) is a subset of traces(A), fairtraces(B) is a subset of fairtraces(A) -----------------------------------------------------------------------------