More Web Proxy on the site http://driver.im/

article

Trade-offs Between the Size of Advice and Broadcasting Time in Trees

Authors:

Emanuele G. Fusco,

Andrzej PelcAuthors Info & Claims

Algorithmica, Volume 60, Issue 4

Pages 719 - 734

Published: 01 August 2011 Publication History

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 O(nź), for an arbitrarily small positive constant ź. This is the first communication problem for which a trade-off between the size of advice and the efficiency of the solution is shown for arbitrary size of advice.

References

[1]

Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 547---556

Digital Library

[2]

Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 290---298 (1991)

Digital Library

[3]

Awerbuch, B., Goldreich, O., Peleg, D., Vainish, R.: A tradeoff between information and communication in broadcast protocols. J. ACM 37, 238---256 (1990)

Digital Library

[4]

Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. Inf. Comput. 176, 1---21 (2002)

Digital Library

[5]

Chierichetti, F.: Personal communication (2009)

[6]

Clementi, A.E.F., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proc. 12th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 709---718

Digital Library

[7]

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Proc. 32th International Colloquium on Automata, Languages and Programming (ICALP 2005). LNCS, vol. 3580, pp. 335---346

Digital Library

[8]

Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: Proc. 44th Symp. on Foundations of Computer Science (FOCS 2003), pp. 492---501

[9]

Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theor. Comput. Sci. 326, 343---362 (2004)

Digital Library

[10]

Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. J. Discrete Algorithms 5, 187---201 (2007)

Digital Library

[11]

Diks, K., Kranakis, E., Krizanc, D., Pelc, A.: The impact of knowledge on broadcasting time in linear radio networks. Theor. Comput. Sci. 287, 449---471 (2002)

Digital Library

[12]

Elkin, M., Kortsarz, G.: A sublogarithmic approximation algorithm for the undirected telephone broadcast problem: a path out of a jungle. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 76---85

[13]

Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distributed Comput. 16, 121---163 (2003)

Digital Library

[14]

Fraigniaud, P., Gavoille, C., Ilcinkas, D., Pelc, A.: Distributed computing with advice: information sensitivity of graph coloring. In: Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007). LNCS, vol. 4596, pp. 231---242

[15]

Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication problems. In: Proc. 25th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2006), pp. 179---187

[16]

Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). LNCS, vol. 4162, pp. 24---37

[17]

Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: Proc. 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), pp. 154---160

Digital Library

[18]

Gavoille, C., Peleg, D., Pérennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 210---219

[19]

Ilcinkas, D., Kowalski, D., Pelc, A.: Fast radio broadcasting with advice. In: Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008). LNCS, vol. 5058, pp. 291---305

[20]

Katz, M., Katz, N., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 927---936

[21]

Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC 2005), pp. 9---18

Digital Library

[22]

Kortsarz, G., Peleg, D.: Approximation algorithms for minimum time broadcast. SIAM J. Discrete Math. 8, 401---427 (1995)

Digital Library

[23]

Kowalski, D., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distrib. Comput. 18, 43---57 (2005)

Digital Library

[24]

Kowalski, D., Pelc, A.: Optimal deterministic broadcasting in known topology radio networks. Distrib. Comput. 19, 185---195 (2007)

Digital Library

[25]

Lynch, N.: A hundred impossibility proofs for distributed computing. In: Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC 1989), pp. 1---28

Digital Library

[26]

Pelc, A.: Activating anonymous ad hoc radio networks. Distrib. Comput. 19, 361---371 (2007)

Digital Library

[27]

Proskurowski, A.: Minimum broadcast trees. IEEE Trans. Comput. C-30(5), 363---366 (1981)

Digital Library

[28]

Slater, P.J., Cockayne, E.J., Hedetniemi, S.T.: Information dissemination in trees. SIAM J. Comput. 10, 692---701 (1981)

[29]

Soguet, D., Nisse, N.: Graph searching with advice. In: Proc. 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2007). LNCS, vol. 4474, pp. 51---65

[30]

Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1---24 (2005)

Digital Library

Cited By

Gorain BMiller APelc AAgrawal KAzar Y(2021)Four Shades of Deterministic Leader Election in Anonymous NetworksProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461794(265-274)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461794
Gąsieniec LStachowiak G(2020)Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader ElectionJournal of the ACM10.1145/342465968:1(1-21)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3424659
Dieudonné YPelc A(2019)Impact of Knowledge on Election Time in Anonymous NetworksAlgorithmica10.1007/s00453-018-0444-381:1(238-288)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00453-018-0444-3
Show More Cited By

Trade-offs Between the Size of Advice and Broadcasting Time in Trees
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Trade-offs between the size of advice and broadcasting time in trees
SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures

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. ...
Fast radio broadcasting with advice

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and ...
Fast Radio Broadcasting with Advice
SIROCCO '08: Proceedings of the 15th international colloquium on Structural Information and Communication Complexity

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with <em>advice</em>. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Algorithmica

Algorithmica Volume 60, Issue 4

August 2011

312 pages

ISSN:0178-4617

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media, LLC.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gorain BMiller APelc AAgrawal KAzar Y(2021)Four Shades of Deterministic Leader Election in Anonymous NetworksProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461794(265-274)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461794
Gąsieniec LStachowiak G(2020)Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader ElectionJournal of the ACM10.1145/342465968:1(1-21)Online publication date: 17-Nov-2020
https://dl.acm.org/doi/10.1145/3424659
Dieudonné YPelc A(2019)Impact of Knowledge on Election Time in Anonymous NetworksAlgorithmica10.1007/s00453-018-0444-381:1(238-288)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00453-018-0444-3
Gorain BPelc A(2018)Deterministic Graph Exploration with AdviceACM Transactions on Algorithms10.1145/328082315:1(1-17)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3280823
Gorain BPelc A(2018)Finding the Size of a Radio Network with Short LabelsProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154298(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154298
Dieudonné YPelc AScheideler CHajiaghayi M(2017)Impact of Knowledge on Election Time in Anonymous NetworksProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087563(207-215)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087563
Glacet CMiller APelc A(2017)Time vs. Information Tradeoffs for Leader Election in Anonymous TreesACM Transactions on Algorithms10.1145/303987013:3(1-41)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/3039870
Glacet CMiller APelc A(2016)Time vs. information tradeoffs for leader election in anonymous treesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884479(600-609)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884479
Miller APelc AScheideler CGilbert S(2016)Election vs. SelectionProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/2935764.2935772(377-386)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2935764.2935772
Fusco EPelc APetreschi R(2016)Topology recognition with adviceInformation and Computation10.1016/j.ic.2016.01.005247:C(254-265)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.01.005
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents