Homework 9

22C:116, Spring 1995

Due Friday Apr. 14, 1995, in class.

1. Background: Consider the problem of electing a process from among a set of processes on an arbitrary tree structured network (or on the spanning tree of an arbitrary graph structured network). Each process i has a set Ni, the neighbors of i. A process may send messages to its neighbors and it may receive messages from its neighbors.

   The state Si of each process is either Normal, in which case the process is not participating in an election, Conducting, in which case it is the root of the tree involved in conducting an election, Subtree, in which case it is conducting part of an election over a subtree, or Result, in which case, it is awaiting a result. After the completion of an election, the state should return to Normal.

   In addition, the state of a process includes Ci, the identity of the process that called the election that process i is currently participating in, and Ri, the identity of a neighbor closer to the root of the current election, and Ei, the result of the most recent election. Each of these is only valid in some of the states of each process.

   There are a number of message types, including Elect. When a process receives a message of type Elect, if it was in state Normal, it enters state Subtree and sends those messages necessary to conduct an election.

   The Problem, part A: for each message a process may receive, indicate the state change that occurs in that process and the messages it sends to its neighbors; both the state change and the messages sent may depend on the state and on the contents of the message it receives. The result should be a complete specification of an election protocol.

   The Problem, part B: In what states does the receipt of what messages imply that two elections have collided, for example, as the result of simultaneous initiations of two elections at two processes at the same time? Modify your protocol so that it guarantees that only one of the two colliding elections will be completed.

2. Problem: Given the definition of a tree structured network and the approach taken to specifying a protocol over that network given above, can you specify a distributed mutual exclusion protocol for such a network?

3. Background: Consider a system with multiple processes, where all interprocess communication uses semaphores and shared memory. A real-time-clock is available, and the P operation on a semaphore is a function with accepts a second parameter, a time delay; if the P operation blocks and this time delay elapses, it unblocks and returns false. If the P operation does not block for longer than this, it returns true.

   The only failures that concern us on this system are failures of a process. That is, we assume that memory is fully reliable. Assignment of a pointer or integer can be done as an atomic operation, at the machine level, but assignment of floating point numbers is not atomic -- it requires multiple load or store operations.

   Problem: Write code to atomically increment a shared floating point variable.