Article

Radio communication in random graphs: extended abstract

Authors:

Robert Elsässer,

Leszek GasieniecAuthors Info & Claims

SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

Pages 309 - 315

https://doi.org/10.1145/1073970.1074021

Published: 18 July 2005 Publication History

Abstract

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the broadcasting problem in random radio networks. In particular we show how to perform a centralized broadcast in a random graph Gp=(V,E) of size n=|V| and expected average degree d=pn in time O(ln n/lnd+lnd). Later we present a randomized distributed broadcasting algorithm with the running time O(ln n). In both cases we show that the presented algorithms are asymptotically optimal by deriving lower bounds on the complexity of radio broadcasting in random graphs. In these proofs we determine some structural properties in random graphs which may be of independent interest. We should note here that the results of this paper hold with probability 1-o(1/n).

References

[1]

A. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.]]

[2]

B. Bollobás. Random Graphs. Academic Press, 1985.]]

[3]

B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures and Algorithms, 18:279--290, 2001.]]

Digital Library

[4]

D. Brusci and M. D. Pinto. Lower bounds for the broadcast problem in mobile radio networks. Distributed Computing 10, pages 129--135, 1997.]]

Digital Library

[5]

H. Chen. Threshold of broadcast in random graphs. DIMACS Tech. Rep. 97--12, 1997.]]

Digital Library

[6]

H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat., 23:493--507, 1952.]]

[7]

I. Chlamtac and S. Kutten. On broadcasting in radio networks-problem analysis and protocol design. IEEE Transactions on Communications 33, pages 1240--1246, 1985.]]

[8]

B. Chlebus, L. Gasieniec, A. Östlin, and J. Robson. Deterministic radio broadcasting. Proc. of ICALP'00, pages 717--728, 2000.]]

Digital Library

[9]

B. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, and W. Rytter. Deterministic broadcasting in unknown radio networks. Proc. of SODA'00, pages 861--870, 2000.]]

Digital Library

[10]

M. Chrobak, L. Gasieniec, and W. Rytter. Fast broadcasting and gossiping in radio networks. Journal of Algorithms 43(2), pages 177--189, 2002.]]

Digital Library

[11]

F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6:125--145, 2002.]]

[12]

F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Internet Mathematics, 1:91--114, 2003.]]

[13]

F. Chung, L. Lu, and V. Vu. Eigenvalues of random power law graphs. Annals of Combinatorics, 7:21--33, 2003.]]

[14]

A. Clementi, A. Monti, and R. Silvestri. Selective families, superimposed codes, and broadcasting in unknown radio networks. Proc. of SODA'01, pages 709--718, 2001.]]

Digital Library

[15]

K. Diks, E. Kranakis, D. Krizanc, and A. Pelc. The impact of knowledge on broadcasting time in radio networks. Proc. of ESA'99, pages 41--52, 1999.]]

Digital Library

[16]

M. Elkin and G. Kortsarz. Improved broadcast schedule for radio networks. Proc. of SODA'05, 2005.]]

[17]

R. Elsässer, U. Lorenz, and T. Sauerwald. Agent-based information handling in large networks. Proc. of MFCS'04, pages 586--598, 2004.]]

[18]

U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithm, 1(4):447--460, 1990.]]

[19]

A. Frieze and M. Molloy. Broadcasting in random graphs. Discrete Applied Mathematics 54, pages 77--79, 1994.]]

Digital Library

[20]

I. Gaber and Y. Mansour. Broadcast in radio networks. Proc. of SODA'95, pages 577--585, 1995.]]

Digital Library

[21]

E. Gilbert. Random graphs. Ann. Math. Statist. 30, pages 1141--1144, 1959.]]

[22]

L. Gasieniec, A. Pagourtzis, and I. Potapov. Deterministic communication in radio networks with large labels. Proc. of ESA'02, pages 512--524, 2002.]]

Digital Library

[23]

L. Gasieniec, D. Peleg, and Q. Xin. Faster centralised communication in radio networks. Manuscript, 2005.]]

[24]

T. Hagerup and C. Rüb. A guided tour of Chernoff bounds. Information Processing Letters, 36(6):305--308, 1990.]]

Digital Library

[25]

R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. Proc. of FOCS, 2000.]]

Digital Library

[26]

G. D. Marco and A. Pelc. Faster broadcasting in unknown radio networks. Information Processing Letters 79(2), pages 53--56, 2001.]]

Digital Library

[27]

M. Mihail and C. Papadimitriou. On the eigenvalue power law. Proc. of RANDOM'02, pages 254--262, 2002.]]

Digital Library

[28]

M. Mihail, C. Papadimitriou, and A. Saberi. On certain connectivity properties of the internet topology. Proc. of FOCS'03, pages 28--35, 2003.]]

Digital Library

[29]

P. Erdös and A. Rényi. On random graphs I. Publ. Math. Debrecen 6, pages 290--297, 1959.]]

[30]

P. Erdös and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, pages 17--61, 1960.]]

[31]

A. Sen and M. Huson. A new model for scheduling packet radio networks. Proc. of 15th Ann. Joint Conference of the IEEE Computer and Communication Societies, pages 1116--1124, 1996.]]

Digital Library

Cited By

Berenbrink PCooper CHu Z(2009)Energy efficient randomised communication in unknown AdHoc networksTheoretical Computer Science10.5555/1540666.1541119410:27-29(2549-2561)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.5555/1540666.1541119
Berenbrink PCooper CHu Z(2009)Energy efficient randomised communication in unknown AdHoc networksTheoretical Computer Science10.1016/j.tcs.2009.02.002410:27-29(2549-2561)Online publication date: Jun-2009
https://doi.org/10.1016/j.tcs.2009.02.002
Berenbrink PHu ZCooper CGibbons PScheideler C(2007)Energy efficient randomised communication in unknown AdHoc networksProceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures10.1145/1248377.1248419(250-259)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1248377.1248419
Show More Cited By

Index Terms

Radio communication in random graphs: extended abstract
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the communication complexity of randomized broadcasting in random-like graphs
SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures

Broadcasting algorithms have a various range of applications in different fields of computer science. In this paper we analyze the number of message transmissions generated by efficient randomized broadcasting algorithms in random-like networks. We ...
Radio communication in random graphs
Special issue on network algorithms 2005

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. We propose here several time efficient, centralized as well as fully distributed procedures for the ...
Faster communication in known topology radio networks
PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in radio networks with known topology, i.e., where for each primitive the schedule of transmissions is precomputed based ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

July 2005

346 pages

ISBN:1581139861

DOI:10.1145/1073970

General Chair:
Phil Gibbons
Intel Research
,
Program Chair:
Paul Spirakis
Research and Academic Computer Technology Institute, Greece

Copyright © 2005 ACM.

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: 18 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA05

Sponsor:

SPAA05: 17th ACM Symposium on Parallelism in Algorithms and Architectures 2005

July 18 - 20, 2005

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
261
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Berenbrink PCooper CHu Z(2009)Energy efficient randomised communication in unknown AdHoc networksTheoretical Computer Science10.5555/1540666.1541119410:27-29(2549-2561)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.5555/1540666.1541119
Berenbrink PCooper CHu Z(2009)Energy efficient randomised communication in unknown AdHoc networksTheoretical Computer Science10.1016/j.tcs.2009.02.002410:27-29(2549-2561)Online publication date: Jun-2009
https://doi.org/10.1016/j.tcs.2009.02.002
Berenbrink PHu ZCooper CGibbons PScheideler C(2007)Energy efficient randomised communication in unknown AdHoc networksProceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures10.1145/1248377.1248419(250-259)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1248377.1248419
Chlebus BKowalski DRokicki M(2006)Average-Time complexity of gossiping in radio networksProceedings of the 13th international conference on Structural Information and Communication Complexity10.1007/11780823_20(253-267)Online publication date: 2-Jul-2006
https://dl.acm.org/doi/10.1007/11780823_20

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten