Homework 9 Solutions

22C:116, Fall 1997

Due Monday Nov. 10, 1997, in class

Douglas W. Jones

    Election protocol problem:

    The Problem, part A: What types of messages are there?

    Call Election Message
    Needs only one field: Unique election ID; for this assignment, this can be simply the ID of the vertex that called the election; in more complex election systems, it will also include a serial number.

    Vote Return
    Needs the election ID and the winner being reported.

    Result Broadcast
    Needs the election ID and the winner being reported.

    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
    
  1. The Question: Given a system that is guaranteed to be free of hardware or communications failures, atomic transaction algorithms are still of value for deadlock resolution.

  2. Background: Consider the following computer system:
             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.