Homework 10

22C:116, Fall 2000

Due Friday Nov 3, 2000, in class

1. A Problem Outline (above the pseudocode level) a reasonable implementation of barrier synchronization in an Ada-like language for a 3-way barrier; that is, it should allow 3 processes to rendezvous with a barrier object before any of them are allowed to continue. (You may find it easiest to think about this if you let the barrier have 3 different entries, entry 1, entry 2 and entry 3, where each client has its own dedicated entry to call).

2. A Problem Consider a clock synchronization system where each process synchronizes its clock every second with its nearest neighbors in the network, and where no clock gains or loses more than a millisecond per second relative to the composite average clock rate of the entire system. The system contains 256 clocks. What is the maximum possible error of any one clock relative to any other in this network for each of the following configurations:

   a) The clocks are arranged in a 7-dimensional hypercube.

   b) The clocks are arranged in a 16 by 16 toroidal mesh.

   c) The clocks are arranged in a recursive tetrahedral pyramid

3. A Problem Consider the problems of running an election or obtaining exclusive use of a resource on a recursive tetrahedral network. What key problem must be solved to support either of these? Give a high level description of a solution.