4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ You may want to look at expander graphs, which give exponential growth (up to a point) of the number of people contacted. en.wikipedia.org/wiki/Expander_graph cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf $\endgroup$
    – Douglas Zare
    Commented Mar 7, 2011 at 7:56
  • $\begingroup$ A low valency expander graph is a good solution. However you'd have to give instructions different from the ones I was given when I on a phone trees (usually binary, and a long time ago). We were told that we were responsible for the people below us on the tree. In an expander call graph the edges wouldn't be directed -- so you would have to tell each vertex "You are responsible for making sure these three vertices are contacted." $\endgroup$
    – Sam Nead
    Commented Mar 7, 2011 at 9:02
  • $\begingroup$ Hmmm. Furthermore, a binary tree is easier to design and maintain. I suppose that updating the expander graph could be done by computer... Is there an app for that? $\endgroup$
    – Sam Nead
    Commented Mar 7, 2011 at 9:05

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .