+-------------------+
| Problem Set 2 (a) |
+-------------------+


Problem 1
=========

Grading Policy:

   6 points for correct algorithm
   2 points for proof of new time bound
   2 points for proof of correctness

Majority of the students solved this problem by requiring
the same messages in 2 consecutive rounds. Proof of
correctness is easy (eg. by simulation to the original algorithm),
and all that remains is to prove the new time bound.

Some students solved it by comparing the the current round number
with the number of failed nodes. This can also work.


Problem 2
=========

Part a (7 points)
Recurrence +2
Explanation +3
Final +2

Part b (3 points)
Recurrence +1
Explanation +1
Final +1

There were several ways of approaching this problem (with varying notation)
and for part b there were several possible answers (depending on how
Byzantine you got).


Problem 3
=========

A formal proof along the lines of the AT paper gets a 10. Some
proofs convey the right intuition but are not formal - they got a 9. One of
the guys wrote that consensus is indeed possible, if you assume that an RPC 
service (having a certain functionality) is available. He goes on to add that 
if one doesnt assume an RPC (or a similar service) consensus is impossible, 
and gives a (informal) proof to that effect. He got a 5 for the proof and 2
for the RPC-protocol (since I felt it was right).

Some of the answers mentioned that consensus is impossible, but go on to
give a faulty proof. For example, some answers try to prove that for all 
configurations at round $k$ are bivalent. They got between 4-6 in proportion
to the "correctness" of the proof.


Problem 4
=========

Each threshold (along with the proof) - n+f/2 and 2f+1 - got 5 
points each. If the proofs are incorrect, a proportionate number of points 
are deducted. For example, some answers tried to prove the wrong kind of
inequality. (>=2f instead of >2f)  


Problem 5
=========

Part A: 6 points

+1 point for having the main idea
+3 correct algorithm
+2 correct proof of the algorithm

Part B: 4 points

If you used BFS to simulate Byzantine Agreement:
+1 for having this main idea
+1 for description of how to simulate
+2 if the simulation actually works

If you used the 3-process triangle proof, derived from the proof of BA:
+4 for everyone.  Everyone who attempted this got it right, so I didn't have to
decide on a partial credit criteria.

Common mistakes:

Many algorithms did not correctly synchronize, and thus, failed agreement.  That
was -3.

Some algorithms did not correctly handle a faulty process waking up an arbitrary
subset of processes, or sending "vote" (or the equivalent) messages to an
arbitrary subset at an arbitrary time.  That was -1 or -2, depending on how
reliant the rest of the algorithm was on this not happening.

Some said BFS can't be done for n<=3f because it requires BA as a subroutine.
That was -4.  You can't assume anything about the structure of an algorithm to
prove its impossibility - maybe someone can devise a cool new way to do BFS
without needing BA.

Some said BFS can't be done for n<=3f because it is a very similar problem to
BA, or because BFS requires synchronization (on round number to fire) which is
essentially the same problem as BA.  That was -4.  In theory, BFS round
synchronization can be a simpler problem than BA synchronization, since there is
no validity condition imposed.  Once every process is awake, they can decide on
ANY round number to fire.  Plus, this is a very hand-wavy argument in general.



+-------------------+
| Problem Set 2 (b) |
+-------------------+


Problem 1
=========

In this problem, you were required to extend the result from the paper
to the special case for 1 failure by constructing a chain of executions,
in the same way as we saw in class. Students who gave a detailed proof
with an explicit construction of the chain of executions got a 10. If
the explanation was too short, I removed up to 2 points. If the argument
for the proof did not convince me (too vague, not rigorous enough), I
removed up to 4 points.


Problem 2
=========

Cancelled.


Problem 3
=========

  4 points for the algorithm
  2 points for proof of correctness
  2 points for showing O(n) # of message bound
  2 points for showing early termination (when failure free)

Majority of the students solved this by adding one (or two rounds)
between the original 3rd and 4th round, and use a new
"halt" or "decided" message to notify the fellow nodes.

A small number of students modified the rule for the nodes
(such that when they've decided 0 or 1, they simply halt immediately).
If there are no failures, then this works immediately. Even if there
are failures, these "early halting" nodes would appear to the rest
of the nodes as "stopping failure", which is permitted by
the original 3-phase-commit algorithm. So it also works.


Problem 4
=========

. Trace of A: 2 points
. Trace of B: 4 points
. Trace of AxB: 4 points

Some people forgot to put the empty sequence in some or each of the
traces (-1). Some wrote the executions instead of the trace (-1). Those
who explicitly wrote that the trace of AxB required a finite number of
ack and an infinite number of go or those who did the fair trace as well
got a + (worth the sweat, hey).