Trade-offs between the size of advice and broadcasting time in trees

ABSTRACT

We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of a tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio, taken over n-node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade-off between the size of advice and the best competitive ratio of a broadcasting algorithm for n-node trees. We establish such a trade-off with an approximation factor of On^ε), for an arbitrarily small positive constant ε. This is the first problem for which a trade-off between the amount of provided information and the efficiency of the solution is shown for arbitrary size of advice.

REFERENCES

• 1: Serge Abiteboul , Haim Kaplan , Tova Milo, Compact labeling schemes for ancestor queries, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.547-556, January 07-09, 2001, Washington, D.C., United States
• 2: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 3: Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990 [doi>10.1145/77600.77618]
• 4: Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Information and Computation, v.176 n.1, p.1-21, July 2002 [doi>10.1006/inco.2001.3081]
• 5: Andrea E. F. Clementi , Angelo Monti , Riccardo Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.709-718, January 07-09, 2001, Washington, D.C., United States
• 6: Artur Czumaj , Wojciech Rytter, Broadcasting algorithms in radio networks with unknown topology, Journal of Algorithms, v.60 n.2, p.115-143, August 2006 [doi>10.1016/j.jalgor.2004.08.001]
• 7: Anders Dessmark , Andrzej Pelc, Optimal graph exploration without good maps, Theoretical Computer Science, v.326 n.1-3, p.343-362, 20 October 2004 [doi>10.1016/j.tcs.2004.07.031]
• 8: Anders Dessmark , Andrzej Pelc, Broadcasting in geometric radio networks, Journal of Discrete Algorithms, v.5 n.1, p.187-201, March, 2007 [doi>10.1016/j.jda.2006.07.001]
• 9: Krzysztof Diks , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, The impact of information on broadcasting time in linear radio networks, Theoretical Computer Science, v.287 n.2, p.449-471, 28 September 2002 [doi>10.1016/S0304-3975(01)00256-0]
• 10: Michael Elkin , Guy Kortsarz, Sublogarithmic approximation for telephone multicast: path out of jungle (extended abstract), Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003 [doi>10.1007/s00446-003-0091-y]
• 12: P. Fraigniaud, C. Gavoille, D. Ilcinkas, and A. Pelc. Distributed computing with advice: Information sensitivity of graph coloring. In L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, editors, ICALP, volume 4596 of Lecture Notes in Computer Science, pages 231--242. Springer, 2007.
• 13: Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Oracle size: a new measure of difficulty for communication tasks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146410]
• 14: P. Fraigniaud, D. Ilcinkas, and A. Pelc. Tree exploration with an oracle. In Rastislav Kralovic and Pawel Urzyczyn, editors, MFCS, volume 4162 of Lecture Notes in Computer Science, pages 24--37. Springer, 2006.
• 15: Pierre Fraigniaud , Amos Korman , Emmanuelle Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248402]
• 16: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 17: Michal Katz , Nir A. Katz , Amos Korman , David Peleg, Labeling schemes for flow and connectivity, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.927-936, January 06-08, 2002, San Francisco, California
• 18: Amos Korman , Shay Kutten , David Peleg, Proof labeling schemes, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073817]
• 19: Guy Kortsarz , David Peleg, Approximation Algorithms for Minimum-Time Broadcast, SIAM Journal on Discrete Mathematics, v.8 n.3, p.401-427, Aug. 1995 [doi>10.1137/S0895480193245923]
• 20: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Distributed Computing, v.18 n.1, p.43-57, July 2005 [doi>10.1007/s00446-005-0126-7]
• 21: D. R. Kowalski and A. Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Computing, 19(3):185--195, 2007.
• 22: N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72982]
• 23: N. Nisse and D. Soguet. Graph searching with advice. In G. Prencipe and S. Zaks, editors, SIROCCO, volume 4474 of Lecture Notes in Computer Science, pages 51--65. Springer, 2007.
• 24: A. Pelc. Activating anonymous ad hoc radio networks. Distributed Computing, 19(5-6):361--371, 2007.
• 25: A. Proskurowski, Minimum Broadcast Trees, IEEE Transactions on Computers, v.30 n.5, p.363-366, May 1981 [doi>10.1109/TC.1981.1675796]
• 26: P.J. Slater, E. J. Cockayne, and S. T. Hedetniemi. Information dissemination in trees. SIAM J. Comput., 10(4):692--701, 1981.
• 27: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005 [doi>10.1145/1044731.1044732]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

Keywords:
advice, broadcast, tree