+-------------------+ | Problem Set 5 (a) | +-------------------+ Problem 1 ========= Everyone got this right. Problem 2 ========= a. 5pt (-2 if no mention of snapshoting and incorrect) b. 2 pt for correctness 1 pt for time complexity 1 pt for msg complexity c. 1pt for anything at all Problem 3 ========= part (a): +1 for showing the algorithm doesn't satisfy mutual-exclusion; +1 for showing the correct proof sketch; +1 for showing mutual-exlusion is a safety property; part (b) +1 for showing the algorithm doesn't satisfy no-lockout and correct counter example; +1 for showing no-lockout is a liveness or fairness property; -1 if saying that no-lockout isn't a liveness or fairness property; part (c) +1 for showing the algorithm doesn't satisfy no-deadlock and correct counter example; +1 for showing no-deadlock is a liveness property; part (d) +1 for showing no-lockout and no-starvation are identical; part (e) +1 for showing no-lockout and no-starvation are identical; +1 for showing no-lockout and no-starvation are stonger than (imply) no-deadlock; Problem 4 ========= a) +1 Start from Peterson lock's known mutual exlusion +1 Notice that Peterson lock works only if it has 2 inputs +1 Rest of proof b) +1 No assumptions regarding time/synchronocy, beyond fairness +1 Start from Peterson lock's known lockout-free +1 Notice that induction only works top-down (or else "critical region" of lower-level locks hasn't been proven to terminate) +1 Rest of proof c) +1 Stating (and using) some same-speed-ish assumption +1 Reasonable argument +1 Getting 2^h-1/n-1/O(n) bound -or- +3 Explaining what goes wrong with only fairness -or- +1 Any reasonable argument giving a bound above O(n) Problem 5 ========= +3 Using n-l levels +4 Checking for less than n-l threads above level, instead of 1 +1 Reasonable exculsion proof, based on proof for Filter +2 Reasonable lockout-free proof, based on proof for Filter +-------------------+ | Problem Set 5 (b) | +-------------------+ Problem 1 ========= part a: +1 for recognizing that if the process labels are in a cycle, the timestamp algorithm has failed (this is in the notes) +1 for a valid initial configuration +3 for a (correct) execution that ends in an invalid configuration almost everyone got this right. one mistake was to try to shorten the sequence by having everyone select a label at the same time, and somehow end up selecting labels that form a cycle. unfortunately, this isn't possible. part b: +1 for a correct argument that the labels generated by the timestamping system can have n2^n (or fewer) values +2 for defining partial order that is irreflexive and antisymmetric (and a happy face for a proof) +2 for giving way to produce a new label that dominates all the other threads' labels the problem asks for a "sequential timestamp system that requires only n2^n" values. at the minimum, a "sequential timestamp system" requires a partial order > and a way to generate a label. i don't think giving just one or the other (or neither!) is enough. Problem 2 ========= Filter: - Max points (5) where given for: * stating that level[i] can be regular and victim[l] must be atomic; * giving a conterexample when mutual exlusion is broken when victim[l] is regular; * proving mutual exclusion when level[i] is regular; * proving no-lockout when both variables are regular. - In particular: * 3 points were given for proofs/conterexamples for mutual exclusion; * 2 points were given for proofs of no-lockout. - Generally, 3 points were deducted for people who said that victim[l] can be regular; - It was acceptable to have victim[l] regular when the specific variant of MW regular registers were described (only 1 solution did that); - It was also acceptable to say that victim[l] cannot even be implemented using regular registers because the book claims that regular registers are SW; Bakery: - Max points (5) were given for proofs that all properties hold when all registers are regular; - In particular: * 3 points were given for proofs for mutual exclusion; * 2 points were given for proofs of no-lockout. - A common mistake was that many people referenced the "Distributed Algorithms" book, which stated (on page 296) that the registers are ok to be safe. Note that the book has a different variant of the Bakery - different from the one in the class. Problem statement specifically asked to analyse the algorithm from the class. 3 points were deducted for this mistake. Problem 3 ========= Part a: 7 points 1 points for some descriptive explanation of the algorithm [Some people seemed to just cite the book without describing the algorithm, I wanted more explanation than that.] 4 points for working implementation [Not everyone's actually works.] 2 point for a sufficient explanation/proof/etc. [Again, wanted more than just a citation.] Part b: 3 points 2 points for sequentially consistent implementation [Correctness] 1 point for increased efficiency [As per instructions] Problem 4 ========= 2 points for something that involves snapshot variables and actions [Some people mentioned snapshot variables but didn't even use update/scan, i.e. they just briefly mentioned snapshot variables and proceeded to copy the bakery algorithm without mentioning that you need to update/scan. I wanted some form of snapshot usage. -1 point if partly mentioned but not fully explained.] 3 points for something that actually works [Correctness. -2 if missing some form of choosing functionality; -3 if it just doesn't work.] 2 points for some sufficient explanation/proof/etc. [As per instructions] 3 point for actual increase in efficiency [As per instructions]