Homework 9

22C:116, Spring 1997

Due Friday Apr. 11, 1997, in class

Douglas W. Jones
  1. Background: Not all machines support the same data formats. For example, the DEC Alpha and Intel 80x86 families pack bytes into words in little-endian order, while the Sun SPARC packs bytes into words in big-endian order. IBM mainframes still use the EBCDIC character set instead of ASCII, and while the IEEE floating point format is emerging as a standard, many machines still use other proprietary formats.

    The Problem, part A: Does the ISO OSI protocol hierarchy address this problem? If so, at what level?

    The Problem, part B: In the context of an RPC relationship between client and server, where should any data format conversion required be done?

  2. Background: Consider a system of machines, each with its own local clock, where each machine is connected to some others by point-to-point communications links to form a network. For each link, a clock synchronization algorithm is run once per second to bring the clocks at opposite ends of that link into syncronization.

    The diameter of a network is the longest shortest path in the network. That is, if the length (in point-to-point hops) of the shortest path between i and j is Li,j, then the diameter of the network is maxi,j(Li,j).

    Our clocks are not perfect. Some run slightly fast, and some slightly slow. The maximum rates of clock drift is .01 second per second.

    The Problem, part A: Given that the network has diameter 10, what is the maximum difference that you could observe between any two clocks in the network.

    The Problem, part B: Given that individual clock drift rates are randomly distributed over the allowable range of drift rates, what accuracy would you expect of the composite clock, assuming that there were 100 clocks in the network.

  3. Background: Lamport's bakery algorithm can be trivially distributed across a network, where each process had read-write copies of its state variables and acts as a server, giving values of these variables to other processes in response to requests for them. This trivial conversion to a network algorithm is inefficient because it exchanges far too many messages.

    For this problem, assume point-to-point communications and assume that no knowledge of the network topology is available. Also, assume that you are not free to change the basic synchronization algorithm, but that you are able to optimize it by such means as maintaining local information about the state of remote processes. Note that the relevant state information includes both information about the variables N and C for each process, but also the state of that process (outside, selecting N, waiting entry, inside). Assume that messages are never lost and that processes never die.

    The problem: Optimize Lamport's algorithm for the network context.

  4. The problem, part A: Explain how the mutual exclusion problem and the election problem differ. Answers over one page will be discarded; a good answer can be written as a short paragraph.

    The problem, part A: Explain why some mutual exclusion algorithms can be modified to construct election algorithms, while others cannot. Again, short answers are required!