HW4:
PROBLEM 1: Average: 6.32
1. Grading Policy:
My grading roughly followed this scheme:
3 points for correct algorithm
2 points for correct mutual exclusion
2 points for correct progress
~3 points for something on the higher level guarantees
I broke from the scheme a bit for low scores...The problem is that
if you miss the fairness part of your algorithm, then you can [and most
people did in this case] copy the proofs right out of the book/refer to
the book. Many people had the wrong idea for the progress proof.
2. General Comments:
Many people tried to use proofs from books. There are some technical
details they needed to address that they didn't. IE...Lemma 10.5.3
isn't true for k-exclusion algorithm as stated in book. [The part of
the lemma regarding the S set depends on how people defined their S
sets. Some people carefully defined S to keep this part of the lemma
true.]
PROBLEM 2: Average: 8.6
1. Grading Policy:
I divided the points for this question as follows:
3 - For getting the main idea of the question (i.e. that a process
can delay another process after that process
had finished the first loop)
1 - Proving the time it takes to finish the first loop
2 - Proving the time it takes to finish the second loop
1 - Proving the time it takes from M to C
3- The lower bound example
2. General Comments:
Most of the students got correctly the main point of the question
(that a process can delay another process
after that process had finished the first loop). If a student didn't
look at that possibility, and just looked at the time from when a single
process enters T until it enters C (without taking into account possible
interference by other processes), he lost most of the points for this
question.
Two other problems that appeared in solutions where:
1) Some students wrote that it takes time of O(nl) to finish the first
two loops, while it takes an addition (n^2l) to finish the third one.
This is not true. The time from when the first process enters M until
some process enters C is just 2nl at the most (see the solutions) - and
the really slow loop is the second one.
2) Some students didn't prove correctly the time it takes to finish the
third loop. Its not enough to say that when a process i enters M, all
processes j>i will set their flag to zero in nl time, because it could
be that a process j>i is in his second loop and already passed i in that
loop, so he will enter M too (after i). Now, another process k>j will do
the same thing and enter M as well. So you must say something about the
time this group of processes (j>i) stabilizes, and no more such
processes can enter M.
PROBLEM 3: Average: 8.846153846
In general, most students got the right approach. Everyone stated that the
modified algorithm fails, and over 90 percent of the students stated that
mutual exclusion was violated. The most common problem in students' solutions
is failing to show that number(i) can actually get accumulated to b. I only
deducted 1 point for this problem. There are a few serious problems. For
example, some counterexamples are not stated clearly and tend to be
"hand-waved". I deducted some points according to how clearly the
counterexample is constructed and explained.
PROBLEM 5: Average: 9.18
Grading Scheme:
Part a counts for 8 points, while part b (general case time analysis)
counts for 2 points. For part a, most people saw that the original algorithm
still works for an odd-sized ring, and hence received most of the marks.
The ideal answer is 4c+23l.
For part b, as long as you see that the time bound if O(ck+lk), where k
is k is the length of the longest waiting chain, then you get a full
mark.
Common Mistakes for part a:
1) 1 point is taken off if one did not realize that the upperbound of
S is now different for each process, and instead of simply bounding T
by T <= C + 2l + 2S, a tighter bound would be T <= C + 2l + S + Sn,
where S is the original S in the book, and Sn <= 2c+13l. A lot of
people simply used 2c+13l for S, resulting with a looser upperbound
for T : T<=5c+26l, instead of the tighter bound T<=4c+23l.
2) 1 point is taken off if no detailed time analysis was given and
the resulting time-bound is way too loose. No points were taken off
if there were any small miscaculations in the coefficient of l.
3) 1 point is taken off if the time-bound is way too loose.
Common Mistakes for part b:
1) A number of people forgot to do this part. 2 points are taken off
in this case.
PROBLEM 6: Average: 9.26
Grading Scheme:
1 pt for YES to part(a) 1-failure termination
1 pt for YES to part(b) 1-failure termination
5 pts for correct algorithm for part(a) and (b)
3 pts for understanding the problem and attempting to solve
-1 pt for incomplete or unclear parts
2. General Comments:
Most people either used PetersonNP algorithm or simulated RMW using
PetersonNP. In any case, all correct solutions implemented Mutual
Exclusion. Few stated that there is no algorithm possible for this
problem. Hopefully the sample solution will convince them that it is
possible. Initially, points were taken off for not specifying why the
algorithm guarantees the wait-free and 1-failure termination; however,
these points were given back since the sample solution did not specify
this, problem does not ask for this proof, and it is obvious from the
description of the algorithm.
PROBLEM 7: Average: 9.095
1. Grading Policy:
8 points for a working counter-example.
(ie one that does not exhibit atomicity)
1 point for showing that the example given is actually a valid execution
(ie explain when the reads occur and what values are read etc.)
1 point for explaining why it doesn't show atomicity
(ie the value is never the one reported,
or no serialization corresponds to the output)
+ Since the problem was fairly simple, 10+ was awarded on the basis
of brevity.
2. General Comments:
The problem was fairly easy considering that the solution was easily
drawn from the examples presented in class. Everyone presented a
correct execution.
The only problem anyone had was in explicitly explaining the two key
points of the counterexample
(that it is valid, and that there is no serial explanation).
Since the explanation was very simple (eg "the sum was never the
value output"), and the problem did not ask for a rigorous proof,
these omissions were only slightly penalized.