I was just sent a 'phone tree' by a fellow parent in my kids class.


This is a way for emergency messages to be sent to everyone in the class. They way it works is that you are given a call by the person above you in the list, you are then supposed to call the person below you.


The particular tree in question looks like this (where '+' are people)



```

   +      +
  / \    / \ 
 +   +  +   +
 |   |  |   | 
 +   +  +   +
 |   |  |   | 
 +   +  +   +
 |   |  |   | 
   ..etc ..

```

I am convinced that this is a very bad design in that it will take a long time for a message to propagate to the people at the bottom of the list. For instance if people are away, the message will have to wait for people to check their messages before proceeding to the next person.


Intuitively there appears to be a trade off between efficiency (how many people each person has to call) and reliability/speed of propagation (how many people the message must traverse through before reaching the last person).


I figure this must be a standard network routing problem but in a different guise.


Can someone point me to any papers that examine this problem? I'd especially like to see anything with numerical results - such as 'routing time is a logarithm of number of connections per node' etc. 



Understanding efficiency vs reliability trade offs in a phone tree design
Spreading information is a very important topic in computer science and has many applications, in particular also in network design, as you already mentioned. One well-studied way of doing this is called "Randomized Rumor Spreading". Just use google...


Popular results in this context show that the routing time is logarithmic, if the underlying network has some nice property, like high (vertex/edge) expansion, conductance, and many others.


