Exercise 6.9						Greg Hudson
------------

The message language is V.  Assume all processes know F, the maximum
number of tolerated failures.

states[i] is:
	VAL, a member of V, initially process i's value
	MIN-VAL, a member of V, initially process i's value
	ROUNDS, an integer, initially 0
	DECISION, a member of V + {unknown}, initially unknown

msgs[i] is:
	if ROUNDS < F + 1 then
		Send MIN-VAL to all out-nbrs

trans[i] is:
	ROUNDS := ROUNDS + 1
	Let MIN-RECEIVED be the maximum uid received from a neighbor
	MIN-VAL := max(MIN-VAL, MIN-RECEIVED)
	if ROUNDS = F + 1 then
		DECISION := MIN-VAL

Proof of agreement: If only F processes can fail, then at the
beginning of at least one round (by the pigeonhole principle) all of
the processes successfully send their minimum value to their
neighbors.  At the end of that round, since every process receives all
of the other active process's messages, each process has the same set
of values (received plus their own minimum) to consider, and therefore
has the same min-val.  On all subsequent rounds, no active process's
min-val can change (since all active processes have the same min-val),
so at the end of F + 1 rounds all processes have the same minimum
value and thus all decide on the same value.

Proof of validity: If all processes begin with the same value VAL,
then no process's value will ever change (at the beginning of each
round, every process's MIN-VAL is equal to VAL, so they all send VAL,
and they all decide on a new MIN-VAL equal to VAL regardless of
whether any processes fail), and therefore all processes will decide
on VAL as their value.

Proof of termination: each process terminates after F + 1 rounds.


Exercise 6.24						Greg Hudson
-------------

On round 1, every process sends its initial value to all processes
including itself.  At the end of round 1, each process records the
value received by the most neighbors (call it VAL).  If a process has
receives at least n - f copies of a particular value, it sets VOTE to
1; otherwise, it sets VOTE to 0.

Now invoke the binary Byzantine agreement algorithm using VOTE as the
initial value of each process.  If all the non-faulty processes agree
on 1, they decide on VAL; otherwise they decide on a default value V0.

Agreement: If the binary Byzantine agreement algorithm chooses 0 as
its final value, then every process decides on V0, so in that case
we're set.  Now suppose that the binary agreement algorithm chose 1.
At least one process must have set VOTE equal to 1 (or the binary
agreement algorithm would have chosen 0); thus, that process must have
received at least n - f copies of a particular value (call it VAL0).
Up to f of those copies could have come from faulty processes; the
other n - 2f copies must have come from non-faulty processes.
Therefore, all non-faulty processes must have received n - 2f copies
of VAL0, and therefore recorded VAL0 as their VAL.  So they all decide
on the same value.

Validity: If all the non-faulty processes start with the same value,
then every non-faulty process will recieve at least n - f copies of
that value, and therefore all set VOTE to 1.  The binary Byzantine
agreement algorithm is thus forced to decide on 1, and all processes
decide on their initial values.

Termination: The binary agreement algorithm terminates, and thus ours
does as well (taking only one extra round to do so).


Exercise 6.40						Greg Hudson
-------------

Weak Byzantine agreement algorithm for a two-node connected network:

On round 1, both processes send their initial values to each other.
On round 2, both processes decide on the minimum of their initial
value and the initial value received from the other process.

Agreement: If neither process is faulty, both processes decide on the
minimum of the same set, and thus decide on the same value.  If one or
both processes is faulty, agreement is trivially satisfied since at
most one process decides on a value at all.

Validity: If neither process is faulty and they both start with the
same value (call it VAL), then both processes decide on VAL (since
they decide on the minimum of VAL and VAL).

Termination: Both processes terminate after two rounds.