Douglas W. Jones
The Problem, part A: What types of messages are there?
The Problem, part B:
Variables at each vertex
election_in_progress - initially zero
election_root defined only if election_in_progress nonzero
and this node did not initiate this election.
voted[i] records which neighbors voted in this election
values are no, yes, abstained
winner records the winner of the most recent election when
election in progress is zero
initiate_election:
for each neighbor i,
send( , N[i] )
election_in_progress = my_unique_ID
for all i, voted[i] = no
winner = my_unique_ID
process_election_message( m, n ):
note m is the message, n is the sender ID of the message
case message type of:
Call_Election:
if election_in_progress = m.election_ID
-- prune this branch off the spanning tree
find i such that N[i] = n
send( , N[i] )
else if election_in_progress = 0
-- this is a new election
election_in_progress = m.election_ID
find i such that N[i] = n
election_root = i
for all i extept election_root
send( , i );
voted[i] = no
voted[root] = abstained
winner = my_unique_ID
else if m.election_ID > election_in_progress
this election preempts the election in progress
process exactly as if election_in_progress = 0
Vote_Return:
find i such that N[i] = n
if m.election_ID doesn't match election_in_progress
-- ignore it, that election was preempted!
else
if m.winner = 0
voted[i] = abstained
else
voted[i] = yes
if m.winner > winner then winner = m.winner
if, for all i, voted[i] in {yes, abstained}
if election_in_progress = my_unique_ID
-- results have reached the root!
for all i such that voted[i] = yes
-- send result up spanning tree
send( < result_broadcast, winner>, N[i] )
election_in_progress = 0
else
send( , N[root] )
Result Broadcast:
if m.election_ID doesn't match election_in_progress
-- ignore it, that election was preempted!
else
for all i such that voted[i] = yes
-- send result up spanning tree
send( < result_broadcast, winner>, N[i] )
election_in_progress = 0
M1
____|_____ Bus 1
| |
M-CPU CPU-M
|__________|
| Bus 2
M2
Part A: What concepts from our discussion of atomic transactions are applicable to this system? Clearly, fault tolerance is an issue, as is mutual exclusion. We can use Lamport's notion of stable storage and we can use stable update and pointer assignment to commit transactions. What concepts are inapplicable? We don't need to do 2-phase commit protocols, nor do we need to worry about network protocols, as this is a pure shared memory mutual exclusion problem.
Part B: Assuming that all memory is replicated, so a pointer held in either CPU should point to identical copies of each record when it is interpreted in the context of either memory, we can use Lamport's stable storage update algorithm to update all shared data, and we can organize all of our data as a tree, with dynamically allocated nodes used to record updates, and with stable update of the root used to commit each transaction.