skip to main content
10.1145/1146381.1146410acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Oracle size: a new measure of difficulty for communication tasks

Published: 23 July 2006 Publication History

Abstract

We study the problem of the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. While previous results about communication in networks used particular partial information available to nodes, such as the knowledge of the neighborhood or the knowledge of the network topology within some radius, our approach is quantitative: we investigate the minimum total number of bits of information (minimum oracle size) that has to be available to nodes in order to perform efficient communication.It turns out that the minimum oracle size for which a distributed task can be accomplished efficiently, can serve as a measure of the difficulty of this task. We use this measure to make a quantitative distinction between the difficulty of two apparently similar fundamental communication primitives: the broadcast and the wakeup. In both of them a distinguished node, called the source, has a message, which has to be transmitted to all other nodes of the network. In the wakeup, only nodes that already got the source message (i.e., are awake) can send messages to their neighbors, thus waking them up. In the broadcast, all nodes can send control messages even before getting the source message, thus potentially facilitating its future dissemination. In both cases we are interested in accomplishing the communication task with optimal message complexity, i.e., using a number of messages linear in the number of nodes.We show that the minimum oracle size permitting the wakeup with a linear number of messages in a n-node network, is Θ (n log n), while the broadcast with a linear number of messages can be achieved with an oracle of size O(n). We also show that the latter oracle size is almost optimal: no oracle of size o(n) can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

References

[1]
S. Abiteboul, H. Kaplan, and T. Milo, Compact labeling schemes for ancestor queries. Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2001), 547--556.
[2]
B. Awerbuch, O. Goldreich, D. Peleg and R. Vainish, A trade-off between information and communication in broadcast protocols, Journal of the ACM 37 (1990), 238--256.
[3]
M.A. Bender, A. Fernandez, D. Ron, A. Sahai and S. Vadhan, The power of a pebble: Exploring and mapping directed graphs, Information and Computation 176 (2002), 1--21.
[4]
A.E.F. Clementi, A. Monti and R. Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, Proc. 12th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), 709--718.
[5]
R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman and D. Peleg, Labeling Schemes for Tree Representation. Proc. 7th Int. Workshop on Distributed Computing (IWDC 2005), LNCS 3741, 13--24.
[6]
T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, McGraw-Hill, 1990.
[7]
A. Czumaj and W. Rytter, Broadcasting algorithms in radio networks with unknown topology, Proc. 44th Ann. Symposium on Foundations of Computer Science (FOCS 2003), 492--501.
[8]
A. Dessmark and A. Pelc, Optimal graph exploration without good maps, Theor. Comput. Sci. 326 (2004), 343--362.
[9]
F. Fich and E. Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, 16 (2003), 121--163.
[10]
L. Gasieniec, D. Peleg, and Q. Xin, Faster communication in known topology radio networks, Proc. 24th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2005), 129--137.
[11]
C. Gavoille, D. Peleg, S. Pérennes, and R. Raz, Distance labeling in graphs. Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2001), 210--219.
[12]
T. Kameda and M. Yamashita, Computing on anonymous networks: Part I -- characterizing the solvable cases. IEEE Transactions on Parallel and Distributed Systems, 7 (1996), 69--89.
[13]
M. Katz, N. Katz, A. Korman, and D. Peleg, Labeling schemes for flow and connectivity. Proc. 13th Ann. ACM-SIAM Symp. on Discrete algorithms (SODA 2002), 927--936.
[14]
E. Korach, S. Moran, and S. Zaks, The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors. SIAM J. Comput. 16(2) (1987), 231--236.
[15]
E. Korach, S. Moran, and S. Zaks, Optimal Lower Bounds for Some Distributed Algorithms for a Complete Network of Processors. Theor. Comput. Sci. 64(1) (1989) 125--132.
[16]
A. Korman, S. Kutten, and D. Peleg, Proof labeling schemes. Proc. 24th Ann. ACM Symp. on Principles of Distributed Computing (PODC 2005), 9--18.
[17]
D. Kowalski and A. Pelc, Optimal deterministic broadcasting in known topology radio networks, manuscript.
[18]
F. Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1992.
[19]
N. Lynch. A hundred impossibility proofs for distributed computing. Proc. 8th Ann. ACM Symposium on Principles of Distributed Computing (PODC 1989),1--28.
[20]
M. Thorup and U. Zwick, Approximate distance oracles. Journal of the ACM 52(1) (2005), 1--24.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. broadcast
  2. oracle
  3. wakeup

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)On-line Search in Two-Dimensional EnvironmentTheory of Computing Systems10.1007/s00224-019-09948-6Online publication date: 11-Sep-2019
  • (2019)Network DecontaminationDistributed Computing by Mobile Entities10.1007/978-3-030-11072-7_19(516-548)Online publication date: 13-Jan-2019
  • (2017)The ANTS problemDistributed Computing10.1007/s00446-016-0285-830:3(149-168)Online publication date: 1-Jun-2017
  • (2016)Distributed Evacuation in Graphs with Multiple ExitsStructural Information and Communication Complexity10.1007/978-3-319-48314-6_15(228-241)Online publication date: 4-Nov-2016
  • (2015)Treasure Hunt with AdvicePost-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 943910.1007/978-3-319-25258-2_23(328-341)Online publication date: 14-Jul-2015
  • (2014)Computability in Anonymous Networks: Revocable vs. Irrecovable OutputsAutomata, Languages, and Programming10.1007/978-3-662-43951-7_16(183-195)Online publication date: 2014
  • (2014)Rendezvous of Distance-Aware Mobile Agents in Unknown GraphsStructural Information and Communication Complexity10.1007/978-3-319-09620-9_23(295-310)Online publication date: 2014
  • (2012)Drawing maps with adviceJournal of Parallel and Distributed Computing10.1016/j.jpdc.2011.10.00472:2(132-143)Online publication date: 1-Feb-2012
  • (2012)Memory lower bounds for randomized collaborative search and implications for biologyProceedings of the 26th international conference on Distributed Computing10.1007/978-3-642-33651-5_5(61-75)Online publication date: 16-Oct-2012
  • (2012)Deterministic rendezvous in networks: A comprehensive surveyNetworks10.1002/net.2145359:3(331-347)Online publication date: 1-May-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media