Theory of Design of Telephone Chains
This problem was posed to me many years ago by a political action
group. Their thing was to protest. Whenever something bad happened
they would protest. This meant that when that something bad happened
they wanted to get the word out quickly to everybody. They did this
by calling people on the telephone, who in turn called other people
until everybody was alerted. The problem they ran into was that quite
often a lot of people didn’t get the word.
They wanted to arrange their telephone chain better so that everyone
got the word and asked me how to do it. I thought about it a bit;
this is what I came up with. It’s really a problem in propagation
networks.
This was written in the sixties; it is not a published paper. Editorial comments from the present
are in red. There are a few minor changes in wording.
The basic model for the telephone is genetic transmission. Consider for a moment the convention pyramidal chain in which each person calls several people in the level below them and these in turn call several people below them. We may liken this scheme to the most primitive form of biological reproduction, asexual. This form of transmission has the fundamental flaw that the failure o transmit by any individual results in the failure of transmission to everyone below them. In the original the male gender was assumed as was the practice in those days. Gender neutral language has been used instead. The flaw in the simple pyramid scheme is that each person depends on one and only one person to transmit to them. An obvious way to increase the probability of a person being contacted is to increase the number of people contacting that person. There is an obvious limitation here, in that the number of calls that one person can make is limited. A simple choice is to say that everyone shall be called by two people. This brings us to the basic model of nature, the sexual transmission of genetic information. Under this model each level of the pyramid (which is actually now more like a cross-connected tree or fan) corresponds to a generation. The two people contacting a person correspond to parents, and the people contacted by a person correspond to children. The message to be corresponds to the spread of genetic information. To maximize the amount of transmission we will want to maximize outbreeding. This requirement has several consequences that can be used as criteria for constructing the chain. The most immediate is to maximize the number of ancestors that each individual has. For example, each person has two parents. They might, however, have two, three, or four distinct grandparents. Obviously the fewer the number of grandparents, the greater the probability that all will fail to communicate. Accordingly, one would like to arrange matters so that every one has four distinct grandparents, eight great-grandparents, etc. A second criterion would be that everyone has as many descendents as possible. To see why this is desirable, suppose that everyone on a given level fails to communicate except for one person. Then the number of people who are notified below that level are precisely the descendents of that person. The criterion is indeed desirable but the argument given lacks force. A better statement is that the variance of the number of descendents should be small.A third criterion is that the failure to communicate by a given number of people should affect the least number of people on the level below them. As stated this criterion is rather general and unspecific. However it can be made tighter. Thus it implies that no two parents should have more than one child in common. Similarly no three parents should have more than two children in common. It is clear that I was unfamiliar with error-correcting codes and the design of cryptographic encoding in those days.A fourth criterion is that there are no disjoint sectors. To see what this implies and why it is required suppose that everyone in a given area from the rest of the chain. If this were the chain would appear normal and yet the failure to communicate by a few people at the top would mean the communication to the entire area. A fifth criterion is that the number of generations should be small. This criterion has the obvious point that the lines of communication should be short. The implication is that the fanout, i.e., the rate of increase of cohort size should be large. However increasing fanout rapidly runs into diminishing returns. For example to increase the cohort size by a factor of 1000 requires ten generations if the fanout is 2. Increasing the fanout to 4 cuts the number from 10 to 5. However increasing it by an additional 2 to 6 only cuts the number from 5 to 4.It must be remembered that the genetic analogy is only an analogy. The analogy fails in the following respects: Firstly, all that is required for an individual to receive the message is that any one parent transmits, in contrast to the genetic situation where all parents are required. (In the genetic analogy parents who fail to transmit are like parents carrying a fatal recessive.) Secondly, there is no necessity that the number of parents be two – it could be three or four or an arbitrary number N. Thirdly, and most importantly, the communication in the genetic model is one way, whereas in a telephone chain there is no a priori reason why it could not be both and up and down. Fourthly, of course, there is no restriction of gender in the telephone chain. The third of these considerations is of considerable importance because of the following simple way to increase the reliability of the chain: each person who was supposed to notify them and didn’t. This device has several consequences. It greatly increases the sources of notification for each individual. It also greatly increases the number of paths that the message can travel. These are features that increase the reliability of the chain. There also is the side consequence that anyone in he chain could alert the entire chain. Based on all these considerations we shall try to construct the chain. To them we add two further criteria: We want the total number of calls made by each individual to be small, and secondly that the number of people calling an individual divides the number of people called by the individual. The reason for this requirement is that otherwise things don’t work out evenly and you get fractional people. The choice made in this implementation was that each person be called by two people and call four people. To a certain extent choice is arbitrary, but it can be seen to be reasonable. Other choices are to be called by 2, call 6, called by 3, call 6, called by 2, call 8, etc. Most of these can eliminated by the following consideration: the number depends on the ratio of called to called by. The larger this ratio the more in each generation and the fewer generations needed. For this reason it is better choice is to be called by two people. Of the various choices, the one made was made on the simple basis that it involved the fewest of calls by each individual. The reasoning here is open to question. It is likely that the extra redundancy gained by having three callers rather than two is nominal; however this should have been confirmed rather than guessed. The choices of call six and call eight should have been studied.We now come to the actual construction of the chain. It was started on the assumption that the central office called ten people. (Ten is the smallest number that is compatible with the four grandparents restriction.) From this I made a manually derived list of the first couple of generations. The construction of this list was done on a trial and error basis and represented a considerable amount of playing around. This quickly threatened to involve an exorbitant amount of effort just to ensure that every one called four people and was called by two, let alone more sophisticated requirement. None of this data was included in the paper. Pity.A more sophisticated approach was required. After a little thought the following approach was devised. For each level the members were divided into an upper list and a lower list. The next level to be called was divided into four sections. The lower half called people sequentially; that is, the first person in the lower half called the first four in the next level, the second the second four, etc. The upper half called as follows: The first person in the upper half called the first people in each of the four sectors in the next level. This procedure is simple. A computer program was written to generate the list and punch it out on cards. This was written in the days of FORTRAN and punched cards. The program has not survived. It’s just as well; I don’t have a card reader anymore.A second program was written to read in the list and alterations to the list. This program listed the parents, grandparents, and great-grandparents of each individual. On the basis of these supplementary lists the original list was modified so that every individual had four grandparents and at least seven (and usually eight) great-grandparents. How well does the resultant list check out against the suggested criteria? The answer is – very well, but not perfectly. The criterion of non-localism and the criterion of independence were met by the construction. The criterion of maximized number of ancestors was checked explicitly. The criterion of maximized number of descendents was not explicitly checked but may be expected to be good by the construction. It is unfortunate that the data hasn’t survived, but not very unfortunate. Judging from the analysis I (the “I” of forty years ago) didn’t consider the problem in any great depth. In part this reflects the resources of the time; computers then were slow and expensive. It would be interesting to do an in depth study. This page was last updated April 1, 2006. |