Homework 10 Solutions

22C:116, Fall 2000

A Problem Outline (above the pseudocode level) a reasonable implementation of barrier synchronization in an Ada-like language for a 3-way barrier;

process barrier
   entry p1
   entry p2
   entry p3
begin
   loop
      accept p1
         accept p2
            accept p3
            end accept
         end accept
      end accept
   end loop
forever

A Problem Consider a system of 256 clocks synchronized every second with to their nearest neighbors, where no clock gains or loses more than a millisecond per second. What is the maximum possible error of any one clock relative to any other?
a) The clocks are arranged in a 8-dimensional hypercube.
Two opposite corners are at a distance 8 from each other. Intermediate clocks are can be viewed as being in layers equidistant from the corners, where the population of each layer corresponds to the 9th row of the binomial triangle. The connectivity of this structure is shown in this table:
```
                 neighbors in   neighbors in
row  population  the row above  the row below    speed

 1       1            0              8            fast
 2       8            1              7            fast
 3      28            2              6            fast
 4      56            3              5            fast
 5      70            4              4           mixed
 6      56            5              3            slow
 7      28            6              2            slow
 8       8            7              1            slow
 9       1            8              0            slow
```
We can now simplify this problem, by converting it to a one dimensional problem with just 9 clocks, each of which sets its clock to the simple weighted average of its neighbors, but using a weighted average:
```
          weight of      weight of     weight of
clock   top neighbor  bottom neighbor    self    speed

  1          0              8             1       fast
  2          1              7             1       fast
  3          2              6             1       fast
  4          3              5             1       fast
  5          4              4             1      mixed
  6          5              3             1       slow
  7          6              2             1       slow
  8          7              1             1       slow
  9          8              0             1       slow
```
Symmetry arguments allow us to conclude that the middle clock runs at exactly the average speed for the whole system, and that the error of clock 1 is exactly the same as the error of clock 9, but of opposite sign. The weighted averages used during clock corrections are:
```
t1 = (      t1 + 8t2)/9
t2 = ( t1 + t2 + 7t3)/9
t3 = (2t2 + t3 + 6t4)/9
t4 = (3t2 + t4 + 5t5)/9
```
Iterating these with the 1millisecond gain or loss for every round of clock correction gives the following answer:
```
clock     max error
  1        +7.54
  2        +6.42
  3        +4.97
  4        +2.98
  5         0.0
  6        -2.98
  7        -4.97
  8        -6.42
  9        -7.54
```
(Note that the actual clocks in layer 5 actually will be divided into two groups, half fast, half slow, averaging to zero error. The other numbers are exact. So, we conclude that our extreme clocks will end up 15.8 milliseconds apart, in the worst case.
b) The clocks are arranged in a 16 by 16 toroidal mesh.
The most compact way we can divide the toroid into 2 equal regions, one with fast clocks, one with slow clocks, is to place all the fast clocks in an 8 by 16 patch of the toroid. In this case, the problem quickly reduces to a 1-dimensional loop of 16 clocks, where in computing the averages with nearest neighbors, each clock weights itself 3 times the weight of either neighbor, where the factor of 3 accounts for the neighboring clocks along the dimension of the toroid that we eliminated.
In this loop, the errors will grow progressively from the clocks on the border between fast and slow clocks toward the clocks in the middle of the fast and slow range. Symmetry allows us to argue that the clocks on the border will have equal and opposite errors, while the two clocks in the middle of each range will have equal values. From this, we reduce the problem to 4 clocks. Here are the corrections for these clocks:
```
t1 = (     4t1 + t2)/5  -- middle
t2 = (t1 + 3t2 + t3)/5
t3 = (t2 + 3t3 + t4)/5
t4 = (t3 + 3t4     )/5  -- border
```
Iterating these with the 1millisecond gain or loss for every round of clock correction gives the following answer:
```
clock     max error
  1        +40.0     fast
  2        +35.0
  3        +25.0  
  4        +10.0 __________
  5        -10.0
  6        -25.0
  7        -35.0
  8        -40.0     slow
  9        -40.0   
 10        -35.0
 11        -25.0
 12        -10.0 __________
 13        +10.0
 14        +25.0
 15        +35.0
 16        +40.0      fast
```
So, for the toroid, a structure that is far more loosely connected than the hypercube, the maximum error is 80 milliseconds.
c) The clocks are arranged in a recursive tetrahedral pyramid I'm out of time if you want study questions.
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.
Both of these problems require a broadcast! We can dynamically construct a spanning tree to carry out the broadcast.