Article

Information dissemination in highly dynamic graphs

Authors:

Regina O'Dell,

Rogert WattenhoferAuthors Info & Claims

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

Pages 104 - 110

https://doi.org/10.1145/1080810.1080828

Published: 02 September 2005 Publication History

Get Access

Abstract

We investigate to what extent flooding and routing is possible if the graph is allowed to change unpredictably at each time step. We study what minimal requirements are necessary so that a node may correctly flood or route a message in a network whose links may change arbitrarily at any given point, subject to the condition that the underlying graph is connected. We look at algorithmic constraints such as limited storage, no knowledge of an upper bound on the number of nodes, and no usage of identifiers. We look at flooding as well as routing to some existing specified destination and give algorithms.

References

[1]

Baruch Awerbuch. Reducing complexities of distributed magimum flow and breadth-first search algorithms by means of network synchronization. Networks, 15:425--437, 1985.

Crossref

Google Scholar

[2]

Henri Dubois-Ferriere, Matthias Grossglauser, and Martin Vetterli. Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), 2004.

Digital Library

Google Scholar

[3]

Faith Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. Distributed Computing, 16(2-3), 2003.

Digital Library

Google Scholar

[4]

Eli Gafni and Dimitri Bertsekas. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Transactions on Communications, 29(1), January 1981.

Crossref

Google Scholar

[5]

Zygmunt J. Haas, Marc~R. Pearlman, and Prince Samar. ZRP: A Hybrid Framework for Routing in Ad Hoc Networks. In Ad Hoc Networking. Addison-Wesley, 2001.

Digital Library

Google Scholar

[6]

Marc Heissenbüttel. Networking in Ad-hoc Networks. PhD thesis, University of Bern, CH-3012 Bern, Switzerland, June 2005.

Google Scholar

[7]

David B. Johnson, David A. Maltz, and Josh Broch. DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks. In Ad Hoc Networking. Addison-Wesley, 2001.

Digital Library

Google Scholar

[8]

Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), 2003.

Digital Library

Google Scholar

[9]

Daniel Lang. A comprehensive overview about selected ad hoc networking routing protocols. Technical report, Technische Universität München, Department of Computer Science, March 2003.

Google Scholar

[10]

Moni Naor and Larry Stockmeyer. What can be computed locally? In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), 1993.

Digital Library

Google Scholar

[11]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics (SIAM), 2000.

Digital Library

Google Scholar

[12]

Charles E. Perkins and Elizabeth M. Royer. Ad hoc On-Demand Distance Vector Routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), 1999.

Digital Library

Google Scholar

[13]

Prince Samar, Marc R. Pearlman, and Zygmunt J. Haas. Independent Zone Routing: An Adaptive Hybrid Routing Framework for Ad Hoc Wireless Networks. IEEE/ACM Transactions on Networking (TON), 12(4), 2004.

Digital Library

Google Scholar

Cited By

View all

Di Luna GFlocchini PPrencipe GSantoro N(2024)Locating a Black Hole in a Dynamic RingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104998(104998)Online publication date: Oct-2024
https://doi.org/10.1016/j.jpdc.2024.104998
Mandal SMolla AMoses W(2023)Efficient live exploration of a dynamic ring with mobile robotsTheoretical Computer Science10.1016/j.tcs.2023.114201980(114201)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114201
Kipouridis ESpirakis PTsichlas K(2023)Threshold-based network structural dynamicsTheoretical Computer Science10.1016/j.tcs.2022.12.019944(113669)Online publication date: Jan-2023
https://doi.org/10.1016/j.tcs.2022.12.019
Show More Cited By

Index Terms

Information dissemination in highly dynamic graphs
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

RFC 9667: Dynamic Flooding on Dense Graphs
Performance Enhancements of Ad Hoc Networks with Localized Route Repair

In ad hoc networks, information transfer is achieved in multihop mode using peer-to-peer routing. A route consisting of multihops breaks primarily because of the failure of single or adjacent links, caused by relative movement of one or more nodes. To ...
Neighborhood-Based Route Discovery Protocols for Mobile Ad Hoc Networks

Network-wide broadcasting is used extensively in mobile ad hoc networks for route discovery and for disseminating data throughout the network. Flooding is a common approach to performing network-wide broadcasting. Although it is a simple mechanism that ...

Comments

Information & Contributors

Information

Published In

DIALM-POMC '05: Proceedings of the 2005 joint workshop on Foundations of mobile computing

September 2005

120 pages

ISBN:1595930922

DOI:10.1145/1080810

Program Chairs:
Suman Banerjee
University of Wisconsin-Madison
,
Samrat Ganguly
NEC Laboratories America

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

Dial M - POMC 05

Sponsor:

Dial M - POMC 05: Joint Workshop on Foundations of Mobile Computing 2005

September 2, 2005

Cologne, Germany

Acceptance Rates

Overall Acceptance Rate 21 of 68 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
461
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Di Luna GFlocchini PPrencipe GSantoro N(2024)Locating a Black Hole in a Dynamic RingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104998(104998)Online publication date: Oct-2024
https://doi.org/10.1016/j.jpdc.2024.104998
Mandal SMolla AMoses W(2023)Efficient live exploration of a dynamic ring with mobile robotsTheoretical Computer Science10.1016/j.tcs.2023.114201980(114201)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114201
Kipouridis ESpirakis PTsichlas K(2023)Threshold-based network structural dynamicsTheoretical Computer Science10.1016/j.tcs.2022.12.019944(113669)Online publication date: Jan-2023
https://doi.org/10.1016/j.tcs.2022.12.019
De Carufel JFlocchini PSantoro NSimard F(2023)Cops & Robber on Periodic Temporal Graphs: Characterization and Improved BoundsStructural Information and Communication Complexity10.1007/978-3-031-32733-9_17(386-405)Online publication date: 25-May-2023
https://doi.org/10.1007/978-3-031-32733-9_17
Molla AMoses Jr. W(2022)Dispersion of Mobile RobotsProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3493373(217-220)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3493373
Luna GViglietta G(2022)Computing in Anonymous Dynamic Networks Is Linear2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00108(1122-1133)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00108
Jahja IYu HHou R(2022)On the power of randomization in distributed algorithms in dynamic networks with adaptive adversariesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.09.004159(35-50)Online publication date: Jan-2022
https://doi.org/10.1016/j.jpdc.2021.09.004
Lendl SWoeginger GWulf L(2022)Non-Preemptive Tree PackingAlgorithmica10.1007/s00453-022-01026-785:3(783-804)Online publication date: 23-Aug-2022
https://doi.org/10.1007/s00453-022-01026-7
Bricker RNesterenko MSharma G(2022)Blockchain in Dynamic NetworksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_8(114-129)Online publication date: 9-Nov-2022
https://doi.org/10.1007/978-3-031-21017-4_8
Connor MMichail OSpirakis P(2021)On the Distributed Construction of Stable Networks in Polylogarithmic Parallel TimeInformation10.3390/info1206025412:6(254)Online publication date: 19-Jun-2021
https://doi.org/10.3390/info12060254
Show More Cited By

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

RFC 9667: Dynamic Flooding on Dense Graphs

Performance Enhancements of Ad Hoc Networks with Localized Route Repair

Neighborhood-Based Route Discovery Protocols for Mobile Ad Hoc Networks

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations