+-------------------+
| 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]