-----------------------------------------------------------------------------
PS 2, Problem 1
1. Grading Policy:
Correct modification of the algorithm 3 points
Correct termination argument 1 point
Correct validity proof 3 points
Correct agreement proof 3 points
2. General Comments:
Most students had the correct solution, so there is no major problem
in grading. A few students submitted only the algorithm without the proof,
thus received only partial credit.
-----------------------------------------------------------------------------
PS 2, Problem 2
Grading Policy:
Correct conclusion: 3
Correct understanding of PolyByz procedure: 3
Correct contradiction: 4
-----------------------------------------------------------------------------
PS 2, Problem 3
Grading Scheme for Problem 3:
Part a (6 points):
Most students chose an algorithm that starts an EIGByz subroutine at every
round, each process voting 1 if it had received a wakeup message and 0
otherwise.
The main difficulty most people were faced with was synchronizing the
different rounds of EIGByz that could be off by 1 step because some
processes were dormant when some algorithms started. One solution was to
start each EIGByz algorithm with a "rise and shine" message to everyone, so
that all start simultaneously.
The trick was to understand that if multiple instances of the EIGByz
algorithm were run simultaneously starting at rounds r1, r2, etc, they
would all arrive to agreements at rounds r1+f+1, r2+f+1, and so on. The
synchronicity argument was then trivial, noticing that if rk is the round
at which all non-faulty processes have finally received a wakeup message,
the EIGByz algorithm that started at rk+1 (after the "rise and shine"
message) would conclude at (rk+1)+f+1 with a fire initiative, and that it
would be the first one to arrive at such an agreement.
Grading:
Algorithm idea.....: 2 points
Algorithm details..: 2 points
Proofs.............: 2 points
Part b (4 points):
There were two main groups of solutions, both of them correct.
Solution 1: Reduce ByzAgreement to ByzFire.
Reduction means that given an instance of the ByzAgreement problem, we can
transform it into an instance of ByzFire. Instead of having to solve
ByzAgreement, we can simply solve ByzFire. We have thus "reduced" the
agreement problem into the 'simpler' ByzFire problem. Given an algorithm
that solves ByzFire for n<=3f, we can now solve an instance of ByzAgreement
for n<=3f. Hence the contradiction.
Some students misunderstood the direction of the reduction. Others said
the two problems were equivalent but didn't show either reduction. Some
mistakenly said that "ByzFire is a special case of ByzAgreement" whereas
it's the opposite.
Another common mistake was to say that since our ByzFire was calling
ByzAgreement, and ByzAgreement could not work for n<=3f, ByzFire could not
work either. This is not a proof, since it only argues impossibility if we
use a particular algorithm (with ByzAgreement as subroutine), as opposed to
proving that there is no possible algorithm that can solve ByzFire.
Solution 2: Rebuild the proof from the ground up
Adapt proof in the book (p. 129 section 6.4). A common mistake was to only
show it for n=3 and f=1, without the generalization part.
Grading:
Reduction idea............: 2
Constructing the Reduction: 2
OR:
Base case n=3 and f=1.....: 2
Generalization............: 2
-----------------------------------------------------------------------------
PS 2, Problem 4
There was a wide variation in the algebraic answers
given to this problem. However full points were given
if the students demonstrated an understanding of the algorithm
and came up with an answer that was in the ballpark.
The exact solution was not required.
2-4 points were subtracted per part if the proof technique
clearly was not understood.
1 point subtracted per important error in reasoning.
2 points were taken off the second part if the answer
given was clearly way too short.
1 point was taken off the second part if no estimate
was given of how much shorter the chain would be.
Distribution of points
Part A: 6 points
Part B: 4 points
-----------------------------------------------------------------------------
PS 2, Problem 5
1. Grading Policy:
9 for mostly correct soln, such as k + 1, due to rounding errors
8 mostly correct idea for proof.
7 general idea for proof
5 for mostly wrong answer.
-2 incoherent example
2. General Comments: lots of people had rounding errors, but most did
have the correct idea of proving the bound. Some had very loose
bounds for the soln.
-----------------------------------------------------------------------------
PS 2, Problem 6
1) Grading Policy:
There were many careless mistakes in this problem, but marks were taken off
systematically to be fair to students who spend time in being accurate in
their coding. Furthermore, the book gave a very detailed explanation of
the 3-phase commit protocol, and so more is expected of the code than
otherwise.
Marks are taken off for each of the following mistakes:
1) Failure to give some indication of the case when messages are not
received by a process, or failure to include the null messages "received"
in the cases.
2) Failure to send a message to yourself if you are the leader, or to
initialize the vector in such a way that this is not required, or to do
something of the same effect.
3) Not differentiating the 1st round where initial values are received from
the 3k+1 round for k>1 where status messages are received.
4) Sending to the wrong process, i.e. someone that is not the leader, or
not stating which process to send to, or calculating the wrong process to be
the leader.
5) Forgetting a minor comparison or step.
6) Adding redundant steps to the algorithm thereby forming a modified
algorithm that is not the 3-phase commit. For example, getting every
process to broadcast their status at every round.
7) Not realizing that process 2 can broadcast decide(1) in round 5 whereas
process 1 was unable to do so in round 2.
8) 2 or more parse errors (ambiguous statements). Eg. if (i=k) decide 1 and
current-status=dec1 if (decision = unknown). This could mean:
if (i=k) decide 1; end-if; if (decision = unknown) current-status=dec1, or
it could mean: if (i=k && decision = unknown) decide 1;
current-status=dec1; endif;
9) No clear termination at round=3n.
10) Not realizing that decision="ready" means that a process has not yet
decided.
2 Conceptual Errors (eg. skipping "ready" all the time and going to "dec1")
and Major Mistakes (eg. giving code for the 2 phase commit) were penalized
more heavily.
Notes:
i) Each mistake from the above list will cost a point to be deducted.
ii) For repeated errors, no additional marks were deducted.
iii) Any algorithm that is mostly correct but made numerous careless
mistakes (>5 unique errors) should get at least a 5 or above. i.e. No
student fails for being careless.
iv) The grade distribution was from 3-10.
-----------------------------------------------------------------------------
PS 2, Problem 7
1. Grading Policy:
10 if it was correct, and nothing was wrong
10+ if I thought it was especially easy to understand
9 if it forgot to write down "task" but everything else was right.
7 if it was wrong, but probably because of they forgot something small.
6 if it was wrong.
5 if it was really wrong.
4 if they completely missed the problem altogether, but actually
defined a real automaton
(4 was the lowest)
2. General Comments:
- half were about 10 or 10+.
- most of the 6's were for the same error.(didn't account for
getting a lot of sends before receives, and specified that there
must be no M1 in order to send M2.)
Basically, if they got 5-9: probably one of the following cases didn't work.
m is in M1, n is in M2:
- no n could be received without all the m's being received first.
- getting four n's then an m, and having the m being received first.
There were pretty much only two different solutions. One with one queue,
and another with two queues(and some counting mechanism). There were 2 or
3 different ones(Val's is an example) which did something different.
However, there were 5 that I just couldn't understand, and they're left
ungraded, sorry. They're on top.
-----------------------------------------------------------------------------
PS 2, Problem 8
About B's construction:
(-1) If in the construction of B, one did not differentiate between
locally controlled actions and input actions. e.g. mistake B's
transition: for every s in states(A), pick any single (s,pi,s') from
transitions of A.
(-2) for those who constructed "hyper-states" for B, i.e. a state that
corresponds to a set of different states in A, but failed to describe
what to do with these hyperstates later. (i.e. what's the state
transitions associated with these hyper-states etc) and did not relate
the hyper-states with their arguments about fairtraces. i.e if a state
is not enabled in a "hyperstate" in B, what could we say about the
corresponding executions in A?
Arguing that the fair traces of constructed B is a subset of fairtraces of A.
(-2) for assuming that all executions of A and B are fair by definition
(-2) for assuming that if traces(B) is a subset of traces(A),
fairtraces(B) is a subset of fairtraces(A)
-----------------------------------------------------------------------------