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


Problem 1
=========

+3 for giving the correct sequence within which there is
at least on repeat

+3 for correctly constructint the ring

+3 for correctly analyzing the double rotation
    -1/-2 for misrepresenting the state transition

+1 for reaching the contradiction


Problem 2
=========

O(1) - 2 points
Self-Stabilizing - 3 points
Clock Synch - 2 points
Convincing argument - 3 points


Problem 3
=========

There were 3 approaches to this problem:

approach a: using simulation relations
saying "simulation relation" 1
defining a relation 1
correct relation 2
proving correct relation 4
fairness 2

approach b: claiming 16.8 (this is wrong)
some intuition 2
extra points for using a SimRel from above

approach c: receives happen all at once after sends
some intuition  2
using rounds 2
correct argument 4
actual proof 2



Problem 4
=========

A correct answer may just state the time and communication complexity function
from the book and calculate e' and h.
1. A correct calculation of communication complexity got 5 points.
2. A correct calculation of time complexity got 5 points.
3. One point was subtracted from the total for each step of wrong calculation
(might or might not lead to the correct final answer). 
5. Solutions that showed a mis-understanding of Alpha or Beta or the problem
were subtracted 3 points.
6. A losser bound drived from the ones provided by the book is also accepted
(although not necessary).


Problem 5
=========

For the proof using FloodSet

+2 for pointing out some processes may run very slowly
instead of being failed

+2 for pointing out the delayed processes have different
initial values

+4 for correctly analyzing the behavior of the processes
and GlobSych

+2 for reaching the agreement contradiction.




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


Problem 1
=========

For each property:
2 points for something that removes that property without violating any
other properties.
1/2 point for any application besides 'nothing'.  (was it really that hard
to put *something* down, however nonsensical and amusing it might be?)


Problem 2
=========

1. Simply stating that well-formedness, termination and atomicity are
guaranteed will get 3, 3, and 4 points, respectively. According to the
problem, no proof is needed.

2. If the answer contains explicitly something like the following
points(both), an extra credit will be given: (a) there is no definite
time bound for how long between the bcast event and the response from
a process, but termination is still guaranteed. (b) A brief discussion
about the time cost for a given invocation.


Problem 3
=========

a) 2 points for a correct theorem
b) 4 points for proving each of the 4 properties of logical time correct
under the partial order (1 pt each)
2 points for proving (sketchily) that if two events are dependent they are
related in the p.o., as requested in the definition of weak logical
time--this is actually an implication of the four properties of logical
time, but this must be explicitly stated if that is the only proof
2 points for proving (sketchily) that if they are related by the p.o. then
they are dependent (or the equivalent contrapositive, if they are not
dependent then they are not related by the p.o.)
-1 if only consider direct messages from process i to process j in
dependencies, without considering chains of messages separating two
dependent events, or any other major proof flaw