Problem set 1 problem 2
-----------------------
[I discussed this solution with Jeremy Brown, who had the basic idea
(and the battlefield metaphor).  I worked out the pseudocode and
analysis for my own writeup.]

A message is either "I died" or "I am alive with uid UID".

STATES contains:
	U, of type uid, initially process i's uid
	SEND, of type message, initially "I am alive with uid U"
	STATUS, one of {leader, alive, bleeding, dead, buried}, initially alive

MSGS is
	send the contents of SEND to process i+1

TRANS is
	SEND := null
	if STATUS = buried then
		# Buried people forward all messages.
		SEND := <the message from i - 1, possibly null>
	else if STATUS = dead then
		# Dead people block "I died" messages, but forward uid
		# messages (sinking into the ground as they do so).
		if the message from i - 1 is "I am alive with uid V" then
			# Burial
			STATUS := buried
			SEND := <the message from i - 1>
	else if STATUS = bleeding then
		# Bleeding people die and sink into the ground if they
		# hear from someone else who is alive; if they find
		# out that someone else is dead, they revive.
		if the message from i - 1 is "I am alive with uid V" then
			# Slow death
			STATUS := buried
			SEND := <the message from i - 1>
		else if the message from i - 1 is "I died" then
			# Revival
			STATUS := alive
			SEND := "I am alive with uid U"
	else if STATUS = alive then
		# Alive people elect themselves if their message made
		# it around the network, die quickly if they hear from
		# a live person with a higher UID, and start bleeding
		# if they hear from a live person with a lower UID.
		if the message from i - 1 is "I am alive with uid V" then
			if V = U then
				# Election
				STATUS := leader
			else if V > U then
				# Quick death
				STATUS := dead
				SEND := "I died"
			else
				# Wounding
				STATUS := bleeding
	else if STATUS = leader then
		# Leaders shouldn't ever get any messages, and don't do
		# anything with them if they do.

This algorithm doesn't necessarily elect the process with the maximum
or minimum uid, although it tends to favor processes with higher uids.

It's easiest to think about this algorithm in "stages", although the
stages don't really occur synchronously.  In each stage, the processes
which are alive send "I am alive" messages to the next alive process
(passing over bleeding or dead processes and burying them as they do).
Some number of the alive processes thus become bleeding, and some
become dead.  The ones which become dead send "I died" messages,
reviving the bleeding processor in front of them (if there aren't any
freshly dead processes which already took care of it).  Then the next
"stage" begins (although different processors will become revived at
different times), with at least half of the alive processes buried or
bleeding/dead (they will be buried by the next "I am alive" message).
At least half of them are such because, if there were N processors at
the beginning of the stage, K of them died from uid comparison,
leaving N - K bleeding.  Since only K "I died" messages were sent out,
up to K of the N - K bleeding processes are revived, and K and N - K
can't both be more than half of N.

If there are n processes in the ring, there are O(log(n)) "stages"
with no more than O(n) messages sent per stage (since messages
traverse the arc between each pair of alive processes no more than
twice, once for an "I am alive" message and once for an "I am dead"
message, and the arcs between alive processes total to the size of the
ring).  So O(n*log(n)) messages are sent in the worst case.

We can see that not all of the processes ever die; at any "stage" the
alive process with the highest uid must become bleeding rather than
dying a quick death (so there must be at least one bleeding process)
and the alive process with the lowest uid must die a quick death (so
at least one bleeding process must be revived).

The above proofs are not rigorous because of the asynchrony of the
"stages."  I'm relying on the reader's intuition to see that the
algorithm never gets ahead of itself.  In a sense, this is a bad
algorithm because it is difficult to prove its correctness rigorously
(I couldn't find a useful set of assertions which could be made about
the whole ring in any given time).  But it does satisfy the
requirements of the problem.

Problem set 1 problem 3
-----------------------

[First paragraph wording blatantly stolen from the text, modified for
the new algorithm.]

Computation proceeds in phases 1,2,..., wher each phase consists of n
consecutive rounds.  Each phase is devoted to the possible
circulation, all the way around the ring, of tokens carrying one of k
UIDs.  More specifically, in phase v, which consists of rounds
(v-1)n+1,...,vn, only a token carrying a UID between (v-1)k+1 and vk
inclusive.

The behavior of a process i is as follows: if the message from process
i-1 is a UID token containing UID v, process i forwards the message if
v is less than the process's UID, and elects itself the leader if v is
the same as the process's UID.  After a process i elects itself the
leader, it sends a "I am the leader" token around the ring; if such a
message is received from process i-1, a process halts.  If no message
is received from process u-1, and the current round is numbered
(v-1)n+1 for some v>=1, and the processor's UID is between (v-1)k+1
and vk inclusive, the process sends a message giving its UID to the
next process.

Proof of correctness: Let v0 be the largest integer such that
(v0-1)*k+1 <= UIDmin.  On round (v0-1)n+1, the processor with the
lowest UID sends a message, which will reach itself on round v0n+1, at
which point that processor will elect itself leader.  (According to
the algorithm, the only time a process won't send its UID token on
round (v0-1)n+1 is if it receives a message, which would have to have
been sent n rounds earlier.  Only the process in question could have
sent such a message, and it wouldn't have.) Other processors may also
send messages on round (v0-1)n+1, as well as on round v0n+1, but those
messages will not get past the processor with the lowest UID, so such
processors will never elect themselves the leader.  By round
(v0+1)n+1, when the next batch of processors would have sent messages,
all processors will have received the "I am the leader" token.

Analysis of message complexity: In the worst case, there are 2k
processes numbered (v-1)k+1..(v+1)k for some v>=1.  In this case, all
2k processes get to send messages, which take no more than n rounds to
complete.  Finally, the leader sends an "I am the leader" token around
the ring, for a total complexity of O(2k*n + n) = O(kn) messages.

Analysis of time complexity: since v0 is O(UIDmin/k), and the process
with the minimum UID elects itself leader on round (v0-1)n+1, the time
complexity (including the n rounds for the "I am the leader" token to
go around) is O(n*UIDmin/k).