+-------------------+ | Problem Set 3 (a) | +-------------------+ Problem 1 ========= Part (a): 3 points. -1 point for missing or not showing any of the three safety properties. Some people misread the definition of traces(P) which resulted in the safety properties being incorrect. Part (b): 3 points. Note that there were two possible ways to interpret traces(P), either that every occurrence of 1 is eventually followed by a 2 in a one-to-one correspondence or that every occurrence of 1 is eventually followed by at least one 1. Answers that were correct for either interpretation were accepted. Part (c): 4 points. For full credit, needed to i) explicitly state the safety and liveness properties; ii)show that the safety property was a safety property; iii) show that the liveness property was a liveness property; and iv) argue that P is the intersection of L and S. -1 point if L or S was not explicitly stated or was unclear. -1 point if L or S was incorrect which made the intersection argument incorrect. If the safety and liveness properties were correct, a maximum of 1 point was deducted for neglecting to prove L a liveness property or S a safety property or for failing to argue that P = intersection of L and S. Problem 2 ========= 2 points for each of (a,b,c) in the problem when constructing the IO automaton B (6 points total). Note that many people showed (c) by claiming that the tasks of B contained a single action while also stating that tasks(A)=tasks(B) which does not hold, i.e. there may be a single task of many actions in A. Some people neglected to mention how to construct B such that it has a single start state. Both solutions that built B up from A and solutions that reduced A to B were accepted. Up to 4 points for showing fairtrace inclusion. To receive maximum credit, a solution had to show fairtrace inclusion for both infinite and finite executions of B. 3 points were given for a convincing argument of inclusion while 1 additional point was given for proving inclusion in both infinite and finite executions of B (or showing that infinite induction works). Problem 3 ========= a)(2) +1 correctness/existence of pseudocode +1 correctness of algorithm (if only pseudocode, and is correct, full credit) b)(4) +1 correct simulation relation +2 proof, by induction or other method +1 trace relation is specifically proven c)(4) +2 correct answer +1 sim. rel. +1 proof Notes on grading: The most common point deduction was for not referencing the trace relation, which was specifically requested in the problem. Problem 4 ========= +4 correct pseudocode +3 time complexity +1 correct answer +2 explanation +2 message complexity +1 correct answer +2 explanation Notes on grading: Both O(n log n (l+d)) and O(n (l+d)) time bounds were discussed in the book. I gave credit for either, as long as either appropriate explanation or reference to the book was provided. The example answer was chosen in part because it referenced both possible answers. Problem 5 ========= 6 points for algorithm which correctly solves problem - 3 points for constructing the tree using an algorithm from the book or some other - 3 points for correctly converge-casting the number of nodes back to the source 4 points for proof sketch(most likely using induction on level) - 2 points for statig that we can assume correctness of tree building algorithm - 2 points for showing the source node will get the correct count +-------------------+ | Problem Set 3 (b) | +-------------------+ Problem 1 ========= - 3 points for getting the right answer (the bound doesn't hold) - 3 points for a correct example proof that the bound can be broken (simply showing that the proof doesn't work isn't enough!) - 4 points for showing which parts of the proof were incorrect - showing that the ring construction for two silent processes fails, OR - showing that, in a line, the end-points know that they're not expecting any messages from the other end (as opposed to waiting forever). - (2 points off if the description of the incorrectness of the proof is extremely vague) Problem 2 ========= 6 points for algorithm which correctly solves the problem - 4 points: should modify one of the tree building algorithms in the book - 2 points: must work in O(n(l + d)) time --> O(n^2(l + d)) if they didn't make the same assumption used in the book that all messages can be processed simultaneously. Both will get full credit 4 points for correct time bound proof for above algorithm - 4 points for proving the bound shown in the first part --no points lost if they prove bound which is not as good as O(n(l + d)) they will have already lost points above for not getting the desired time. Problem 3 ========= [part a] 6 points 1 correct bound, O(nlogn(l+d)) 1 max level k <= logn 4 correct proof induction: O(kn(l+d)) from book +1 base case +4 inductive step and correct arguments (3 mostly correct w/some mistakes, but still correct bounds. 1-2 correct but lacking arguments) other: 1-4 depending on how well the proof is written. - ignored waking protocol, since question states that we can assume all procs are woken up as soon as we want them. - some marks if wrong bound, but some arguments given. [part b] 4 points for assertion that bound is tight and a complete argument roughly: +2 execution construction +2 explanation of why execution is O(nlogn(l+d)) 2 points for an execution that is correct but has a different (smaller) bound for instance, serialized exec, with O(n(l+d)) bound <=2 points for an argument for O(nlogn(l+d)) execution that is incorrect wrongly states something about GHS - There are two basic correct constructs for showing O(nlogn(l+d)) from the answers: 1) Arrange processes in a line. Set up weights so that one side of line, through a series of absorbs, forms a (n/2) process component with level 1; the other side forms a series of level 1 components, each with 2 processes. It takes O(logn) merges to combine all these components; and during each merge, we need O(n) messages to broadcast the leader through the biggest component. 2) First arrange procs in a circle with edge weights 1 between each proc. Then add edges so that the graph is a full-mesh, but all other edges have some weight > 1. There are O(logn) merges. In each merge, we need O(n) messages for test messages. In any component with k > 2, there are O(2^k - 2) components which have to send out O(n - 2) test messages. - The serialized execution (all merges) takes O(n(l+d)) time since if there are only merges, the component spanning trees are balanced with height O(k)--each broadcast takes O(k(l+d)) and we sum over logn levels. Problem 4 ========= Most common correct answer: Each proc can read/write from O(1) registers (= 2) and each register is B bits wide. Arrange procs in a ring, by pigeonhole, two will see same vals if n large enough. Cut ring at these two procs, produce two, derive contradiction. Rough point breakdown: +1 construct a special exec with a assumed unique leader (e.g. ring) +3 in some silent exec, two procs end up with same register values. since only 2^K possible reg vals. +2 construct secondary execs, which are indistinguishable from earlier one (e.g. cut ring at procs with same vals, produce two rings) +2 derive contradiction +2 proof completeness and quality Other (partially) correct answers used similar ideas and were given marks based on the quality of their proofs. Problem 5 ========= - 5 points for an algorithm that isn't self-stabilizing - 5 points if it is self-stabilizing - (2 points off for a small flaw) - (4 points off for a big flaw)