Homework 9

22C:116, Fall 1997

Due Monday Nov. 10, 1997, in class

1. Background Recall that, in a network with multiple undirected edges, an election is carried out by broadcasting a call for election, awaiting votes, and then broadcasting the results. The first broadcast in this process builds a spanning tree, and all subsequent operations for this election follow the branches of that tree.

   Assume that each vertex has a unique id, and that each vertex has a local table of neighbors, call it N[i] giving the neighbors of the vertex (i is the index in the table, running from 1 to neighbors, so there is one table entry for each neighbor). The operation send(m,N[i]) will send the message m to the ith neighbor of this vertex. The operation receive(m,i) will block awaiting a message. When the message is received, it is stored in buffer m, and the index i of that neighbor in the receiver's neighbor table N is also returned.

   All messages are tuples , where the types and number of content fields depends on the type. Content fields may themselves be tuples. All messages involved in an election are of type election with any additional details handled in the content fields!

   Assume that each vertex runs the following top-level code:

       repeat
   	if detect failure
               initiate_election()
           else
               receive(msg,m)
               if msg.type = election
   	        process_election_message(msg,i)
               else
                   process_normal_message(msg,i)
               endif
           endif
       forever
   

   You can assume that process_normal_message has something to do with the application.

   The Problem, part A: What message types are involved in the election algorithm, and for each type, what fields are required. Assume that multiple overlapping elections must be detected if they occur, and that overlaps will be resolved by the cancellation of the election originated by the vertex with the lower id.

   The Problem, part B: Write pseudocode for initiate election and for process_election_message.

2. The Question: Given a system that is guaranteed to be free of hardware or communications failures, under what circumstances would atomic transaction algorithms still be of value. Asked in another way, what problems can atomic transaction algorithm solve that are not related to fault tolerance.

3. Background: Consider the following computer system, a simplification of a system actually built at Rockwell International about a decade ago:

            M1
        ____|_____  Bus 1
       |          |
    M-CPU        CPU-M
       |__________|
            |       Bus 2
            M2
   

   In this system, each CPU and each memory module has its own power supply, and the busses are passive and carry no power. Local memory on each CPU is used for code and local variables, so the shared memory modules are used only for shared data. The address space of each CPU is divided into 3 segments, Mlocal, M1 and M2.

   In this question, we are not interested in any I/O devices, but are concerned only with data residing in memory. All synchronization between the 2 CPU's uses busy waiting and algorithms such as Dekker's. Access to individual memory locations is atomic.

   Part A: What concepts from our discussion of atomic transactions are applicable to this system and what concepts are inapplicable.

   Part B: Propose an atomic transaction implementation appropriate for this system.