----------------------------------------------------------------------------- HW3, Problem 1 1. Grading Policy: (i.e., how much you took off for which type of problem, or, alternatively, how much you awarded for each portion of the solution.) Most people did induction, for induction: -3 points was for general understanding of the problem. Basically if you had the idea to use induction you got three points. -2 points was assigned to the base case. Although, this may seem a little harsh but it is very important and crucial to the proof. I took off two points regardless of whether you proved it correctly for base case = size 1. -5 This was for the induction part of the proof. There were four main parts, when new action pi was in(A') show that alpha|A is in traces(A) show that alpha|B' is in traces(B') when new action pi was out(A') show that alpha|A is in traces(A') show that alpha|B' is in traces(B) each was worth 1 point. The last point was basically if you were able to use these to conclude the proof which was fairly obvious if you had these four facts. -some other people came up with solutions different from induction. There was a couple correct ones which recieved tens. Then there were ones that were pretty much just wrong. I gave 2 if you didn't come close. 3 if you had the right idea but had no correct arguments. And 5 points if you made some correct statements, had some idea of what was going on, but any of the correct statements didn't really support the proof. I don't recall any other categrories for people who tried a different solution. 2. General Comments: (i.e., notes about different solutions and typical problems you encountered.) Many people missed the base case, saying that it was 1 instead of 0. Also people thought that you can excahnge B and B' because it looks the same from A's persepective, but forgot to realize that B and B' are different and an action of A could also be an action of B that is enabled in B' but not in B thus it wouldn't be in the trace of (A'xB). For those people who didn't split it up into the 2 cases, "in" and "out" I took off points as if you did, so as to be fair to the people who did. Therefore, failing to prove one thing in one case, could be worth 2 points if it wasn't completely obvious that you would have solved it for the other cases. Also, solving it for one case also doesn't imply that you get it for the other case if it wasn't completely obvious. ----------------------------------------------------------------------------- HW 3, Problem 2 General remarks & grading policy -------------------------------- Though not difficult, this problem was very long and error-prone. It tested the standard techniques for automaton specification and simulation proofs. Unfortunately, a huge number of people seem not to understand the IOA model and the attached techniques; people with bad grades are strongly encouraged to reread Chapter 8. There have been some ambiguities in the problem text: for example, it was not very clear if Pi is a user process using the service or just an interface between the service and the user process Ui. Also, the definition of the totally ordered broadcast service didn't mention explicitly that the deliver ordering should be compatible with the FIFO ordering. As the problem was very long and many people worked a lot on it, I tried to be VERY generous; I didn't take points off for many errors but I wrote my comments for every detected error (because our goal is to help people learn, not to give bad grades). The grades are ranging from 0 to 10+ with an average of 8.5. Common problems: * The problem text required explicitly the use of the FIFO reliable channels lo link Pi with S in both directions. Unfortunately, many people didn't use them. As this was not critical in this problem, I didn't take points off for it. However, the direct connection between Pi and S accounts for an instantaneous network link which is not realistic at all. * The specification C must guarantee that all the recipients receive the same messages, in the same order (and the FIFO order should be preserved because C is an extension to B; otherwise, you cannot do any simulation). This does not imply that this ordering is the same as that of the incoming bcast(m)i requests. Many people (90%) did this mistake of overspecification. Again, I didn't take points off for this error. * There are many errors related to the IOA model. Some common errors: - an input action is always enabled; it cannot have a Precondiction clause; - a transition is not a program: you cannot perform actions inside the Effect clause. This clause is only the specification of the final state of the transition (by difference from the initial state, specified by the Precodition clause, if any); - the transitions are performed one at a time; it is not legal to perform n simultaneous actions; - as an input action is always enabled, if you don't want to lose messages, you usually need to use a queue to store the previous messages; - the specification of a I/O Autoamaton include Signature, States + Start States, Transitions and Tasks. Nothing is optional in this specification; - states should be specified in a resonable mathematical language. Specification like "States: remembers the sequence of messages ..." cannot be accepted; - the only way for automata to comunicate is by some common action; if their sets of actions are disjoint, there is no communication at all; - the simulation proof must have the standard form presented in the Chapter 8. This includes: mapping function, start condition and step condition; - the step condition is not just about moving from one state to another, but also about trace(alpha)=trace(pi); after all, the reason we are doing simulation proofs is to determine that two automata have the same trace; - obviously from the previous consideration, automaton A1 cannot simulate A2 unless they have the same external interface. Many people seem to ignore this ... I took one point off for each one of these errors. * Some people tacitly supposed that the sets of messages sent by each Pi are disjoint or, equivalently, each mesage has a kind of source identifier in it. As this is a reasonable supposition, if the rest was good, I didn't take points off for it. However, the normal solution requires tagging each message with its sender. * I found three identical solutions (modulo the names). Students are encouraged to collaborate and exchange ideas but, anyway, they are expected to do more than just printing the same errors three times. I didn't take any point for this (thir grades were low enough) but try to be fair toward your classmates! * The points were distributed as follows: 6 points for a and c (they were very similar) and 4 points for b and d. I tried to grade the method and not the details. For a and c, I took points for errors in IOA specification and for automata that don't meet the problem' specifications. For b and d, people who didn't use the standard simulation proof received only 1 point (partial credit). Statistics ---------- Graded solutions: 42 "Missing" people: 14 Average grade: 8.5 ----------------------------------------------------------------------------- HW 3, Problem 3 1. Grading Policy: Part a. 5: correct and efficient algorithm 4: correct and efficient algorithm with wrong (but reasonable) assumption 3: correct algorithm but with unnecessary complexity 1-2: incorrect Part b. 5: Convincing argument 4. argument with some minor inconsistency 1-3: didn't give a related argument 2. General Comments: Most students did very well on this problem. Some students got point deducted because they didn't fully use the condition given by the problem and thus got higer message complexity based on their assumption. On the other hand, some students based their algorithm on conditions not explicitly stated by the problem (such as end point knows whether it is left-most or right-most or whether it has left or right nbrs), thus 0 message needed. I deduct one point off for this case. ----------------------------------------------------------------------------- HW 3, Problem 4 1. Grading Policy: The algorithm was worth 4 points, and the proof was worth 6 points. An algorithm lost one point if its tasks, signature and transitions were defined incompatibly, and up to 4 points for general brokenness. A proof generally lost one point for each wrong bound, one point for missing safety, one for missing liveness, and one for failing to prove BFS. Not all grumbling in red actually resulted in lost points if the offense was minor. 2. General Comments: There were two general approaches to this problem, one in which all acks were tracked (which had a time bound of O(n^2*(l+d))) and another in which only acks for the most recent distance were tracked (which had a time bound of O(diam*n*(l+d))). People using the latter approach often failed to send an ack to the old parent when switching parents with an ack still pending, which would cause the algorithm to fail. Another common error, in algorithms where acks were generated only by recieve, was a failure to handle the case of a network-topological leaf node correctly: this was a very subtle difficulty, however, so I did not generally note it or take points off. Finally, some algorithms could not terminate with a finite fair trace, but that seemed a matter of interpretation, and did not incur point loss. There were three main errors people encountered in formulating their proofs. The first and most important was a tendency to prove either liveness or safety, but not both. It was vital to show both that the algorithm would eventually terminate *and* that it would not terminate until the BFS tree had converged. A few other individuals seemed to believe that stating that "an inductive proof is possible" was a sufficiently detailed sketch. Finally, a number of people attempted to prove that process i could not generate an ack until its parent had reached its final value, an assertion which is not true - there is a counterexample where a neighbor of i believes it is at an equal distance to i until after it sends an ack, at which point it discovers that it should actually be i's parent. ----------------------------------------------------------------------------- HW 3, Problem 5 1. Grading Policy: part a (7 points) - 5 , - 6, -7 - induction not used, or used improperly - 4 merge/absorb time complexity not analysed - 3 merge/absorb time complexity mentioned but the the case when the adjacent components have a different mwoe is not specifed - 2 the case when adjacent componets have a diffenet mwoe mentioned but time complexity not analysed - 1 base case missing part b (3 points) - binary (either sombody gave the correct answer or not) 2. General Comments: Part a: All who received most of the points solved the problem similarly to the solution you gave me. The five students who received 10+ solved the problem exactly the same as the solution you gave me. I have not noticed any other correct solutions to the problem. Part b: All who received 3pts specified a construction of the graph and the execution of the algorithm (similar to your solution). Some students were specifying an execution with merges only - O(n(l+d) ) -- no points were given in this case. ----------------------------------------------------------------------------- HW 3, Problem 6 Grading Scheme and General Comments: Many people approached this problem using either the CountMoney algorithm presented in Chap. 18 or the ChandyLamport algorithm of Chap. 19. Both were equally good solutions. Several other excellent algorithms were presented as well. Even if you did use one of the algorithms from the book, I expected a description of the algorithm and an explanation of the correctness. As far as grading was concerned most people started at 10 and were discounted according to the following scheme (The mark values are maximum deductions). Algorithm correctness and description (3 marks): If the presented algorithm was incorrect, or incompletely presented some marks were deducted. Delay (2 marks) : The problem stated that the chosen algorithm should not cause undue delays in the underlying transactions. Minimally invasive schemes were possible so some marks could be lost here. Over-specification (2 marks): The counting scheme should impose and assume very little about the transaction protocol. Algorithms that imposed artificial restrictions were penalized. Correctness Goals (1 mark): What does correctness of the protocol mean? I was looking for something along the lines of "All money is counted exactly once." Correctness Argument (2 marks): A reasonable argument for the correctness of the algorithm. This did not have to be rigorous. A relatively informal sketch was fine. If citing the book, I still wanted to know what the proof was showing. ----------------------------------------------------------------------------- HW 3, Problem 7 1. Grading Policy: -4 for doing Beta within a cluster and Alpha on the forest of clusters (this was usually the only deduction I made in this case) -2 for looking at the wrong tree or cluster layout -1 for not using the best possible spanning tree, as instructed in the problem statement (i.e. root of cluster at center) -1 for not explaining where their value of h came from (whether correct or not) -1 for not explaining where their value of e' came from (whether correct or not) -1 for getting incorrect h -1 for getting incorrect e' -1 for using too loose a bound on e' -1 for forgetting r or m in the complexity expressions I tried to be a little more lenient when there was a decent discussion, even when the answer was not correct. 2. General Comments: Fairly straightforward problem. Most people took the same approach, starting with expressions for complexity given on page 552 of the text. Some went back to the complexities of the Alpha and Beta sub-problems. Several people did not properly explain where they got their values for h & e'. In a problem this short, that has to count for something! Some people mixed up the Gamma algorithm by applying Beta within a cluster and Alpha on the forest of clusters (should be the other way around) A couple of students did not use the right grid/cluster configuration, and assumed complete graphs, which led them to the wrong answer. It should also be noted that several groups of students had the exact same wording for their solutions. I did not deduct any marks, but I made a note on their sheets, telling them that collaboration is OK, however they should write up their own solution to show that they understand it. ----------------------------------------------------------------------------- HW 3, Problem 8 2 pts : State algorithm is wrong for soln 1: 3 pts : State it violates the agreement condition 5 pts : Show clearly how the agreement condition is violated. for soln 2: 8 pts : for stating that if the algorithm is correct, it would violate Thm 21.2 Most people showed that the algorithm violated the agreement condition of consensus problem with stopping failure and provided good example excutions. A couple students used the violation of Thm 21.2 solution. There were usually no problems, except a few people's soln were either completely hand waving or their arguement for agreement violation were not entirely correct.