+-------------------+
| Problem Set 3 (a) |
+-------------------+
Problem 1
=========
Part (a): 3 points. -1 point for missing or not showing any of the three
safety properties. Some people misread the definition of traces(P) which
resulted in the safety properties being incorrect.
Part (b): 3 points. Note that there were two possible ways to interpret
traces(P), either that every occurrence of 1 is eventually followed by a 2
in a one-to-one correspondence or that every occurrence of 1 is eventually
followed by at least one 1. Answers that were correct for either
interpretation were accepted.
Part (c): 4 points. For full credit, needed to i) explicitly state the
safety and liveness properties; ii)show that the safety property was a
safety property; iii) show that the liveness property was a liveness
property; and iv) argue that P is the intersection of L and S.
-1 point if L or S was not explicitly stated or was unclear. -1 point if L
or S was incorrect which made the intersection argument incorrect. If the
safety and liveness properties were correct, a maximum of 1 point was
deducted for neglecting to prove L a liveness property or S a safety
property or for failing to argue that P = intersection of L and S.
Problem 2
=========
2 points for each of (a,b,c) in the problem when constructing the IO
automaton B (6 points total). Note that many people showed (c) by
claiming that the tasks of B contained a single action while also stating
that tasks(A)=tasks(B) which does not hold, i.e. there may be a single
task of many actions in A. Some people neglected to mention how to
construct B such that it has a single start state. Both solutions that
built B up from A and solutions that reduced A to B were accepted.
Up to 4 points for showing fairtrace inclusion. To receive maximum credit,
a solution had to show fairtrace inclusion for both infinite and finite
executions of B. 3 points were given for a convincing argument of
inclusion while 1 additional point was given for proving inclusion in both
infinite and finite executions of B (or showing that infinite induction
works).
Problem 3
=========
a)(2)
+1 correctness/existence of pseudocode
+1 correctness of algorithm (if only pseudocode, and is correct, full credit)
b)(4)
+1 correct simulation relation
+2 proof, by induction or other method
+1 trace relation is specifically proven
c)(4)
+2 correct answer
+1 sim. rel.
+1 proof
Notes on grading:
The most common point deduction was for not referencing the trace relation,
which was specifically requested in the problem.
Problem 4
=========
+4 correct pseudocode
+3 time complexity
+1 correct answer
+2 explanation
+2 message complexity
+1 correct answer
+2 explanation
Notes on grading:
Both O(n log n (l+d)) and O(n (l+d)) time bounds were discussed in the book. I
gave credit for either, as long as either appropriate explanation or reference
to the book was provided. The example answer was chosen in part because it
referenced both possible answers.
Problem 5
=========
6 points for algorithm which correctly solves problem
- 3 points for constructing the tree using an algorithm from the book or
some other
- 3 points for correctly converge-casting the number of nodes back to
the source
4 points for proof sketch(most likely using induction on level)
- 2 points for statig that we can assume correctness of tree building
algorithm
- 2 points for showing the source node will get the correct count
+-------------------+
| Problem Set 3 (b) |
+-------------------+
Problem 1
=========
- 3 points for getting the right answer (the bound doesn't hold)
- 3 points for a correct example proof that the bound can be broken
(simply showing that the proof doesn't work isn't enough!)
- 4 points for showing which parts of the proof were incorrect
- showing that the ring construction for two silent processes
fails,
OR
- showing that, in a line, the end-points know that they're not expecting any messages from the other end (as opposed to waiting
forever).
- (2 points off if the description of the incorrectness of the proof
is extremely vague)
Problem 2
=========
6 points for algorithm which correctly solves the problem
- 4 points: should modify one of the tree building algorithms in the
book
- 2 points: must work in O(n(l + d)) time --> O(n^2(l + d)) if they
didn't make the same assumption used in the book that all messages
can
be processed simultaneously. Both will get full credit
4 points for correct time bound proof for above algorithm
- 4 points for proving the bound shown in the first part
--no points lost if they prove bound which is not as good as O(n(l + d))
they will have already lost points above for not getting the
desired time.
Problem 3
=========
[part a]
6 points
1 correct bound, O(nlogn(l+d))
1 max level k <= logn
4 correct proof
induction: O(kn(l+d)) from book
+1 base case
+4 inductive step and correct arguments
(3 mostly correct w/some mistakes,
but still correct bounds.
1-2 correct but lacking arguments)
other: 1-4 depending on how well the proof is written.
- ignored waking protocol, since question states that we can assume
all procs are woken up as soon as we want them.
- some marks if wrong bound, but some arguments given.
[part b]
4 points for assertion that bound is tight and a complete argument
roughly: +2 execution construction
+2 explanation of why execution is O(nlogn(l+d))
2 points for an execution that is correct but has a different (smaller)
bound
for instance, serialized exec, with O(n(l+d)) bound
<=2 points for an argument for O(nlogn(l+d)) execution that is incorrect
wrongly states something about GHS
- There are two basic correct constructs for showing O(nlogn(l+d)) from
the answers:
1) Arrange processes in a line. Set up weights so that one side
of line, through
a series of absorbs, forms a (n/2) process component with
level 1; the other side
forms a series of level 1 components, each with 2 processes.
It takes O(logn)
merges to combine all these components; and during each
merge, we need O(n)
messages to broadcast the leader through the biggest
component.
2) First arrange procs in a circle with edge weights 1 between
each proc.
Then add edges so that the graph is a full-mesh, but all
other edges have
some weight > 1. There are O(logn) merges. In each merge, we
need O(n)
messages for test messages. In any component with k > 2,
there are O(2^k - 2)
components which have to send out O(n - 2) test messages.
- The serialized execution (all merges) takes O(n(l+d)) time since if
there are only merges,
the component spanning trees are balanced with height O(k)--each
broadcast takes O(k(l+d))
and we sum over logn levels.
Problem 4
=========
Most common correct answer:
Each proc can read/write from O(1) registers (= 2) and each register
is B bits wide. Arrange procs in a ring, by pigeonhole, two will see
same vals if n large enough. Cut ring at these two procs, produce two,
derive contradiction.
Rough point breakdown:
+1 construct a special exec with a assumed unique leader (e.g. ring)
+3 in some silent exec, two procs end up with same register values.
since only 2^K possible reg vals.
+2 construct secondary execs, which are indistinguishable from earlier
one
(e.g. cut ring at procs with same vals, produce two rings)
+2 derive contradiction
+2 proof completeness and quality
Other (partially) correct answers used similar ideas and were given
marks based on the quality of their proofs.
Problem 5
=========
- 5 points for an algorithm that isn't self-stabilizing
- 5 points if it is self-stabilizing
- (2 points off for a small flaw)
- (4 points off for a big flaw)