Exercise 18.5						Greg Hudson
-------------
(A) Here is the code for SampleBank[i].  In this algorithm, each
process begins with a balance of 100 and tries to achieve a balance of
50 by sending money to some neighbor.  If a process has a balance of
50, it will still send 0 to its neighbors at regular intervals, so
each process sends an infinite number of messages to its neighbors.

	Signature:
		Input:
			receive(n)[j,i], n a natural number, j in nbrs
		Output:
			send(n)[i,j], n a natural number, j in nbrs

	States:
		balance, a natural number, initially 100

	Transitions:
		receive(n)[j,i]
			Effect:
				balance := balance + n
		send(n)[i,j]
			Precondition:
				n = balance - 50
			Effect:
				balance := 50

	Tasks:
		For every j in nbrs and every natural number n:
			{send(n)[i,j]}

(B) Here is the code for TimedSampleBank[i], using the Lamport
algorithm for logical time.

	Signature:
		Input:
			receive(n, c)[j,i], n,c natural numbers, j in nbrs
		Output:
			send(n,c)[i,j], n,c natural numbers, j in nbrs

	States:
		balance, a natural number, initially 100
		clock, a natural number, initially 0

	Transitions:
		receive(n,c)[j,i]
			Effect:
				clock := max(clock, c) + 1
				balance := balance + n
		send(n,c)[i,j]
			Precondition:
				n = balance - 50
				c = clock + 1
			Effect:
				clock := c
				balance := 50

	Tasks:
		For every j in nbrs and every natural number n and c:
			{send(n,c)[i,j]}

(C) Assuming we have a globally known logical time t, here is
CountingSampleBank[i]:

	Signature:
		Input:
			receive(n, c)[j,i], n,c natural numbers, j in nbrs
		Output:
			send(n,c)[i,j], n,c natural numbers, j in nbrs
			report(n)[i], n a natural number

	States:
		balance, a natural number, initially 100
		clock, a natural number, initially 0
		synchbal, a natural number or null, initially null
		synchnbrs, a subset of nbrs, initially empty
		reported, a boolean, initially false

	Transitions:
		receive(n,c)[j,i]
			Effect:
				clock := max(clock, c) + 1
				if clock > t then
					if synch = null then
						synchbal := balance
					if c > t then
						synchnbrs := synchnbrs + {j}
					else
						synchbal := synchbal + n
				balance := balance + n
		send(n,c)[i,j]
			Precondition:
				n = balance - 50
				c = clock + 1
			Effect:
				clock := c
				if clock > t then
					if synch = null then
						synchbal := balance
				balance := 50
		report(n)[i]
			Precondition:
				n = synchbal
				synchnbrs = nbrs
				reported = false
			Effect:
				reported = true
				clock := clock + 1

	Tasks:
		For every j in nbrs and every natural number n and c:
			{send(n,c)[i,j]}

(Obviously, when clock <= t, synchbal is null and is thus not equal to
any natural number n, so a report action cannot take place since
report is restricted to reporting natural numbers.)

As the book suggests, we could determine t by using a predetermined
sequence of logical times T, running the algorithm in parallel for
each t, broadcasting our results, and reporting for the first run of
the algorithm which succeeds.

Exercise 19.5						Greg Hudson
-------------
We will run DijkstraScholten in parallel on each node.  Each message
from the original algorithm will be tagged with the id of the process
which received the original input for that part of the computation
(the "source process"), and the status, parent, send-buffer, and
deficit queues will be indexed by the source process uid.  When a
process i becomes quiescent, it can send acks to its parent for any
part of the computation for which i has a deficit(k) of 0 for each
neighbor k.  From the reasoning about DijkstraScholten, each source
process i will execute done[i] when its own part of the algorithm
completes; thus, when all source processes execute done[i], the
algorithm must have reached a global quiescent state.


Exercise 19.7
Greg Hudson
-------------
(A) The global state returned by the snapshot is $14, $18, and $26,
with the channel from 3 to 2 containing a $2 message.  So process 1
must record its state after receiving $5 from process 3 but before
receiving $4 from proces 2.  Process 2 must record its state after
sending $3 to process 3 but before receiving $2 from process 3.
Process 3 must record its state after sending $5 to process 1.  A
possible execution is:

					(1 at $10, 2 at $20, 3 at $30)
	send($1)[1,2]			(1 at $9)
	receive($1)[1,2]		(2 at $21)
	send($2)[3,2]			(3 at $28)
	send($3)[2,3]			(2 at $18)
	snap[2]				(2 records $18)
	send(marker)[2,1]
	send(marker)[2,3]
	receive($2)[3,2]		(2 records $2 from 3 to 2) (2 at $20)
	receive($3)[2,3]		(3 at $31)
	send($5)[3,1]			(3 at $26)
	receive($5)[3,1]		(1 at $14)
	receive(marker)[2,1]		(1 records $14) (channel-snapped(2)[1])
	send(marker)[1,2]
	send(marker)[1,3]
	receive(marker)[2,3]		(3 records $26) (channel-snapped(2)[3])
	send(marker)[3,1]
	send(marker)[3,2]
	receive(marker)[1,2]		(channel-snapped(1)[2])
	receive(marker)[1,3]		(channel-snapped(1)[3]) (3 ready)
	report($26, ((), (), ()))[3]
	receive(marker)[3,1]		(channel-snapped(3)[1]) (1 ready)
	report($14, ((), (), ()))[1]
	receive(marker)[3,2]		(channel-snapped(3)[2]) (2 ready)
	report($18, ((), (), ($2)))[2]

(B) I'm not sure what it means to "generalize the result of part (A)".
If you want a particular global snapshot returned, you pick a process
whose outgoing message channels are all recorded as empty by the
snapshot, run snap there when it has the correct monetary value, let
it receive any messages it's supposed to record on incoming channels,
deliver the marker messages to its neighbor processes when they have
the correct monetary values, let them receive messages they're
supposed to record on incoming channels, and so forth until all
processes have received the marker.  Then deliver any remaining
messages.