Exercise 6.45						Greg Hudson
-------------

To see how long the chain of executions is, let's define a(i) to be
the length of the chain executions (not counting the first execution)
needed to establish that two executions have equivalent results if a
single process's input is changed at the beginning of round i, where
by "input is changed at the beginning of round i", we mean that the
initial value of a process is changed if i = 0, or that a message
which was received at round i in one execution was not received in the
other, if i > 0.

a(f) is 1+2(n-f) as follows: in our proof, to establish that two
executions are identical if the input of one process (call it j) is
changed at round f, we first assume that f-1 other processes have
halted previously.  Then we turn off the messages from j to the other
n-f processes one by one until they are all off (n-f executions).
Then we change the input of process j at round f (one execution).
Finally, we turn the messages from j to the other n-f processes back
on one by one again until process j didn't fail at all (n-f
executions).  This takes a total of 1+2(n-f) executions.

a(i) for i<f is 1+2(n-i)a(i+1) as follows: we proceed just as before
(assuming that only i processes have failed previously, not f), except
that turning off a message from j to another process (call it k) now
takes a(i+1) executions instead of just one execution, since we have
to establish equivalence when the input of process k changes at round
i+1.

Our total number of executions is 1+n*a(0), since we need one
execution to start with, plus a(0) executions to show that the result
must be the same if the input of each processes is changed at the
beginning of round 0 (i.e. the initial value of each process is
changed).  This gives:

	Total executions	= 1 + na(0)
				= 1 + n(1 + 2(n-1)a(1))
				= 1 + n(1 + 2(n-1)(1 + 2(n-2)a(2)))
				.
				.
				.
				= theta(2^f * n!/(n-f)!)

If we can use Byzantine failures, we can shorten the first part of the
of executions at each level: to show that two executions have
equivalent results if process j's input is changed at the beginning of
round i, change the input to process j at the beginning of round i and
have process j lie to all the other processes as if it had the same
input as in the previous execution.  We still have to "wake up"
process j in the normal method, i.e. by restoring its message to other
processes one by one.  If we let b(i) be the analog of a(i) for
Byzantine failures, then b(f)=1+(n-f) and b(i) = 1+(n-i)b(i+1) for
i<f.  This gives:

	Total executions	= 1 + nb(0)
				= 1 + n(1 + (n-1)b(1))
				= 1 + n(1 + (n-1)(1 + (n-2)b(2)))
				.
				.
				.
				= theta(n!/(n-f)!)

So we've removed the 2^f factor.

Exercise 7.1					Greg Hudson
------------

If you only run the FloodMin k-agreement algorithm for floor(f/k)
rounds, in the worst case k stopping failures occur during each round.
(If fewer failures occur during some round, then at most k values are
chosen by the logic in the proof that the algorithm works if you run
it for floor(f/k)+1 rounds.)  If k stopping failures occur in a round,
at most k+1 minimum values are held in a subsequent round (again, by
the same logic as in the proof), so at most k+1 minimum values are
held by processes at the end of the execution.


Exercise 7.10					Greg Hudson
-------------

(a) If you don't reduce W, a Byzantine process could send to some
process (call it process j) a value which is very small compared to
the other process's values.  Since select() takes the minimum value,
select(W) will include this very small value, and mean(select(W))
could be skewed an arbitrary amount downwards.  So you don't get any
convergence if you use mean(select(W)), and the algorithm doesn't
solve the approximate agreement problem.

(b) If you compute mean(reduce(W)), then all of the values in
reduce(W) are in the set of non-faulty process' values.  In the worst
case, f Byzantine processes conspire to make process j take the mean
of the lowest two thirds of the non-faulty processes, and process j'
take the mean of the highest two thirds, but even in this case we
should get some convergence (a sixth of the spread, I think).  So this
algorithm solves the approximate agreement problem, but slowly.

(c) mean(W) is even worse than mean(select(W)).  A Byzantine process
could introduce a very small value into the calculation in the same
manner as in (a).  So such an algorithm doesn't solve the approximate
agreement problem.


Exercise 10.3					Greg Hudson
-------------

Suppose we modify DjikstraME so that set-flag-2i sets pc to leave-exit
instead of check, thus eliminating the second flag-checking stage of
DjikstraME.  Then we can construct a execution where DjikstraME
doesn't satisfy the mutual exclusion property.  Our execution will
involve two processors (1 and 2), and have turn initially set to 2.

Our actions are as follows:

	Action			Read/write operation
	------			--------------------
	try[1]
	set-flag-1[1]		flag(1) <-- 1
	test-turn[1]		turn --> 2
	test-flag(2)[1]		flag(2) --> 0
	try[2]
	set-flag-1[2]		flag(2) <-- 1
	test-turn[2]		turn --> 2
	set-turn[1]		turn <-- 2
	set-flag-2[1]		flag(1) <-- 2
	set-flag-2[2]		flag(2) <-- 2

and both processes proceed to go to the critical region, violating the
mutual exclusion property.  The key here is that process 2 does
set-flag-1 and test-turn between process 1's test-flag(2) and
set-turn.  The second stage of DjikstraME resolves this kind of race
condition by having whichever process sets its flag to 2 last fail the
check stage (the other process might fail as well, but at least one of
the processes has grabbed turn and will succeed the next time around).


Exercise 10.4					Greg Hudson
-------------

Assertion 10.3.5: In any reachable system state, if pc[i] is in
{check, leave-try, crit, reset}, then flag(i) = 2.

This is proved by induction on the length of an execution.  Since each
pc[i] is try at the beginning of the execution, we have the basis
case.  Assume that assertion 10.3.5 holds at the beginning of a
transition; then the only transitions which might violate the
condition are set-flag-2[i], check(j)[i], crit[i], and exit[i] (all
other transitions leave the antecedent false).  set-flag-2[i]
satisfies the consequent of the condition by setting flag(i) to 2.
check(j)[i] and crit[i] have the consequent of the condition true at
the beginning of the transition by the induction assumption.  For
exit[i] you need the implicit assumption that exit[i] is only reached
from crit[i] through transitions which don't set flag(i) (that is,
through code which is isn't our state variables).  (If you were to
literally follow the code on page 258, you could instead prove by a
very simple induction that exit[i] is never reached at all.)  At any
rate, none of the transitions will violate the condition and thus
assertion 10.3.5 holds.