-----------------------------------------------------------------------------
HW3, Problem 1
1. Grading Policy: (i.e., how much you took off for which
type of problem, or, alternatively, how much you awarded
for each portion of the solution.)
Most people did induction, for induction:
-3 points was for general understanding of the problem.
Basically if you had the idea to use induction you got
three points.
-2 points was assigned to the base case. Although, this may seem a
little harsh but it is very important and crucial to the proof.
I took off two points regardless of whether you proved it correctly
for base case = size 1.
-5 This was for the induction part of the proof.
There were four main parts,
when new action pi was in(A')
show that alpha|A is in traces(A)
show that alpha|B' is in traces(B')
when new action pi was out(A')
show that alpha|A is in traces(A')
show that alpha|B' is in traces(B)
each was worth 1 point. The last point was basically
if you were able to use these to conclude the proof
which was fairly obvious if you had these four facts.
-some other people came up with solutions different from induction.
There was a couple correct ones which recieved tens. Then there were
ones that were pretty much just wrong. I gave 2 if you didn't
come close.
3 if you had the right idea but had no correct arguments. And 5
points if you made some correct statements, had some idea of what
was going on, but any of the correct statements didn't really support
the proof. I don't recall any other categrories for people who tried
a different solution.
2. General Comments: (i.e., notes about different solutions and
typical problems you encountered.)
Many people missed the base case, saying that it was 1 instead
of 0. Also people thought that you can excahnge B and B'
because it looks the same from A's persepective, but forgot to
realize that B and B' are different and an action of A could
also be an action of B that is enabled in B' but not in B thus
it wouldn't be in the trace of (A'xB). For those people who
didn't split it up into the 2 cases, "in" and "out" I took off
points as if you did, so as to be fair to the people who did.
Therefore, failing to prove one thing in one case, could be
worth 2 points if it wasn't completely obvious that you would
have solved it for the other cases. Also, solving it for one
case also doesn't imply that you get it for the other case if
it wasn't completely obvious.
-----------------------------------------------------------------------------
HW 3, Problem 2
General remarks & grading policy
--------------------------------
Though not difficult, this problem was very long and error-prone. It
tested the standard techniques for automaton specification and
simulation proofs. Unfortunately, a huge number of people seem not to
understand the IOA model and the attached techniques; people with bad
grades are strongly encouraged to reread Chapter 8. There have been
some ambiguities in the problem text: for example, it was not very
clear if Pi is a user process using the service or just an interface
between the service and the user process Ui. Also, the definition of
the totally ordered broadcast service didn't mention explicitly that
the deliver ordering should be compatible with the FIFO ordering.
As the problem was very long and many people worked a lot on it, I
tried to be VERY generous; I didn't take points off for many errors
but I wrote my comments for every detected error (because our goal is
to help people learn, not to give bad grades). The grades are ranging
from 0 to 10+ with an average of 8.5.
Common problems:
* The problem text required explicitly the use of the FIFO reliable
channels lo link Pi with S in both directions. Unfortunately, many
people didn't use them. As this was not critical in this problem, I
didn't take points off for it. However, the direct connection between
Pi and S accounts for an instantaneous network link which is not
realistic at all.
* The specification C must guarantee that all the recipients receive the same
messages, in the same order (and the FIFO order should be preserved because
C is an extension to B; otherwise, you cannot do any simulation). This
does not imply that this ordering is the same as that of the incoming
bcast(m)i requests. Many people (90%) did this mistake of overspecification.
Again, I didn't take points off for this error.
* There are many errors related to the IOA model. Some common errors:
- an input action is always enabled; it cannot have a Precondiction clause;
- a transition is not a program: you cannot perform actions inside the
Effect clause. This clause is only the specification of the final state
of the transition (by difference from the initial state, specified by the
Precodition clause, if any);
- the transitions are performed one at a time; it is not legal to perform
n simultaneous actions;
- as an input action is always enabled, if you don't want to lose messages,
you usually need to use a queue to store the previous messages;
- the specification of a I/O Autoamaton include Signature, States + Start
States, Transitions and Tasks. Nothing is optional in this specification;
- states should be specified in a resonable mathematical language.
Specification like "States: remembers the sequence of messages ..." cannot
be accepted;
- the only way for automata to comunicate is by some common action; if
their sets of actions are disjoint, there is no communication at all;
- the simulation proof must have the standard form presented in the
Chapter 8. This includes: mapping function, start condition and
step condition;
- the step condition is not just about moving from one state to another, but
also about trace(alpha)=trace(pi); after all, the reason we are doing
simulation proofs is to determine that two automata have the same trace;
- obviously from the previous consideration, automaton A1 cannot simulate
A2 unless they have the same external interface. Many people seem to ignore
this ...
I took one point off for each one of these errors.
* Some people tacitly supposed that the sets of messages sent by each
Pi are disjoint or, equivalently, each mesage has a kind of source
identifier in it. As this is a reasonable supposition, if the rest was
good, I didn't take points off for it. However, the normal solution
requires tagging each message with its sender.
* I found three identical solutions (modulo the names). Students are
encouraged to collaborate and exchange ideas but, anyway, they are
expected to do more than just printing the same errors three times. I
didn't take any point for this (thir grades were low enough) but try
to be fair toward your classmates!
* The points were distributed as follows: 6 points for a and c (they
were very similar) and 4 points for b and d. I tried to grade the
method and not the details. For a and c, I took points for errors in
IOA specification and for automata that don't meet the problem'
specifications. For b and d, people who didn't use the standard
simulation proof received only 1 point (partial credit).
Statistics
----------
Graded solutions: 42
"Missing" people: 14
Average grade: 8.5
-----------------------------------------------------------------------------
HW 3, Problem 3
1. Grading Policy:
Part a. 5: correct and efficient algorithm
4: correct and efficient algorithm with wrong (but reasonable)
assumption
3: correct algorithm but with unnecessary complexity
1-2: incorrect
Part b. 5: Convincing argument
4. argument with some minor inconsistency
1-3: didn't give a related argument
2. General Comments:
Most students did very well on this problem. Some students got point
deducted because they didn't fully use the condition given by the problem
and thus got higer message complexity based on their assumption.
On the other hand, some students based their algorithm on conditions not
explicitly stated by the problem (such as end point knows whether it is
left-most or right-most or whether it has left or right nbrs), thus 0
message needed. I deduct one point off for this case.
-----------------------------------------------------------------------------
HW 3, Problem 4
1. Grading Policy:
The algorithm was worth 4 points, and the proof was worth 6 points.
An algorithm lost one point if its tasks, signature and transitions
were defined incompatibly, and up to 4 points for general brokenness.
A proof generally lost one point for each wrong bound, one point for
missing safety, one for missing liveness, and one for failing to
prove BFS. Not all grumbling in red actually resulted in lost points
if the offense was minor.
2. General Comments:
There were two general approaches to this problem, one in which all
acks were tracked (which had a time bound of O(n^2*(l+d))) and another
in which only acks for the most recent distance were tracked (which
had a time bound of O(diam*n*(l+d))). People using the latter approach
often failed to send an ack to the old parent when switching parents
with an ack still pending, which would cause the algorithm to
fail. Another common error, in algorithms where acks were generated
only by recieve, was a failure to handle the case of a
network-topological leaf node correctly: this was a very subtle
difficulty, however, so I did not generally note it or take points
off. Finally, some algorithms could not terminate with a finite fair
trace, but that seemed a matter of interpretation, and did not incur
point loss.
There were three main errors people encountered in formulating their
proofs. The first and most important was a tendency to prove either
liveness or safety, but not both. It was vital to show both that the
algorithm would eventually terminate *and* that it would not terminate
until the BFS tree had converged. A few other individuals seemed to
believe that stating that "an inductive proof is possible" was a
sufficiently detailed sketch. Finally, a number of people attempted to
prove that process i could not generate an ack until its parent had
reached its final value, an assertion which is not true - there is a
counterexample where a neighbor of i believes it is at an equal
distance to i until after it sends an ack, at which point it discovers
that it should actually be i's parent.
-----------------------------------------------------------------------------
HW 3, Problem 5
1. Grading Policy:
part a (7 points)
- 5 , - 6, -7 - induction not used, or used improperly
- 4 merge/absorb time complexity not analysed
- 3 merge/absorb time complexity mentioned but the the case when
the adjacent components have a different mwoe is not specifed
- 2 the case when adjacent componets have a diffenet mwoe mentioned
but time complexity not analysed
- 1 base case missing
part b (3 points)
- binary (either sombody gave the correct answer or not)
2. General Comments:
Part a: All who received most of the points solved the problem
similarly to the solution you gave me. The five students who received
10+ solved the problem exactly the same as the solution you gave me. I
have not noticed any other correct solutions to the problem.
Part b: All who received 3pts specified a construction of the graph
and the execution of the algorithm (similar to your solution). Some
students were specifying an execution with merges only - O(n(l+d) ) --
no points were given in this case.
-----------------------------------------------------------------------------
HW 3, Problem 6
Grading Scheme and General Comments: Many people approached this
problem using either the CountMoney algorithm presented in Chap. 18 or
the ChandyLamport algorithm of Chap. 19. Both were equally good
solutions. Several other excellent algorithms were presented as
well. Even if you did use one of the algorithms from the book, I
expected a description of the algorithm and an explanation of the
correctness. As far as grading was concerned most people started at 10
and were discounted according to the following scheme (The mark values
are maximum deductions).
Algorithm correctness and description (3 marks): If the presented
algorithm was incorrect, or incompletely presented some marks were
deducted.
Delay (2 marks) : The problem stated that the chosen algorithm should
not cause undue delays in the underlying transactions. Minimally
invasive schemes were possible so some marks could be lost here.
Over-specification (2 marks): The counting scheme should impose and
assume very little about the transaction protocol. Algorithms that
imposed artificial restrictions were penalized.
Correctness Goals (1 mark): What does correctness of the protocol
mean? I was looking for something along the lines of "All money is
counted exactly once."
Correctness Argument (2 marks): A reasonable argument for the
correctness of the algorithm. This did not have to be rigorous. A
relatively informal sketch was fine. If citing the book, I still
wanted to know what the proof was showing.
-----------------------------------------------------------------------------
HW 3, Problem 7
1. Grading Policy:
-4 for doing Beta within a cluster and Alpha on the forest of clusters (this
was usually the only deduction I made in this case)
-2 for looking at the wrong tree or cluster layout
-1 for not using the best possible spanning tree, as instructed in the
problem statement (i.e. root of cluster at center)
-1 for not explaining where their value of h came from (whether
correct or not)
-1 for not explaining where their value of e' came from (whether
correct or not)
-1 for getting incorrect h
-1 for getting incorrect e'
-1 for using too loose a bound on e'
-1 for forgetting r or m in the complexity expressions
I tried to be a little more lenient when there was a decent
discussion, even when the answer was not correct.
2. General Comments:
Fairly straightforward problem.
Most people took the same approach, starting with expressions for
complexity given on page 552 of the text. Some went back to the
complexities of the Alpha and Beta sub-problems.
Several people did not properly explain where they got their values
for h & e'. In a problem this short, that has to count for something!
Some people mixed up the Gamma algorithm by applying Beta within a
cluster and Alpha on the forest of clusters (should be the other way
around)
A couple of students did not use the right grid/cluster configuration,
and assumed complete graphs, which led them to the wrong answer.
It should also be noted that several groups of students had the exact
same wording for their solutions. I did not deduct any marks, but I
made a note on their sheets, telling them that collaboration is OK,
however they should write up their own solution to show that they
understand it.
-----------------------------------------------------------------------------
HW 3, Problem 8
2 pts : State algorithm is wrong
for soln 1:
3 pts : State it violates the agreement condition
5 pts : Show clearly how the agreement condition is violated.
for soln 2:
8 pts : for stating that if the algorithm is correct, it would violate
Thm 21.2
Most people showed that the algorithm violated the agreement condition
of consensus problem with stopping failure and provided good example
excutions. A couple students used the violation of Thm 21.2 solution.
There were usually no problems, except a few people's soln
were either completely hand waving or their arguement for agreement
violation were not entirely correct.