Reliably Detecting Connectivity Using Local Graph Traits
Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global graph properties (connectivity, diameter, girth, etc) have a large influence on...
| Autors principals: | , |
|---|---|
| Altres autors: | |
| Format: | Article |
| Idioma: | en_US |
| Publicat: |
Springer
2011
|
| Accés en línia: | http://hdl.handle.net/1721.1/62568 https://orcid.org/0000-0003-3045-265X |
| _version_ | 1826214515991117824 |
|---|---|
| author | Cornejo Collado, Alex Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Cornejo Collado, Alex Lynch, Nancy Ann |
| author_sort | Cornejo Collado, Alex |
| collection | MIT |
| description | Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global graph properties (connectivity, diameter, girth, etc) have a large influence on the execution of a distributed algorithm.
This paper studies local graph traits and their relationship with global graph properties. Specifically, we focus on graph k-connectivity. First we prove a negative result that shows there does not exist a local graph trait which perfectly captures graph k-connectivity. We then present three different local graph traits which can be used to reliably predict the k-connectivity of a graph with varying degrees of accuracy.
As a simple application of these results, we present upper and lower bounds for a local distributed algorithm which determines if a graph is k-connected. As a more elaborate application of local graph traits, we describe, and prove the correctness of, a local distributed algorithm that preserves k-connectivity in mobile ad hoc networks while allowing nodes to move independently whenever possible. |
| first_indexed | 2024-09-23T16:06:40Z |
| format | Article |
| id | mit-1721.1/62568 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:06:40Z |
| publishDate | 2011 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/625682022-10-02T06:24:03Z Reliably Detecting Connectivity Using Local Graph Traits Cornejo Collado, Alex Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lynch, Nancy Ann Cornejo Collado, Alex Lynch, Nancy Ann Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global graph properties (connectivity, diameter, girth, etc) have a large influence on the execution of a distributed algorithm. This paper studies local graph traits and their relationship with global graph properties. Specifically, we focus on graph k-connectivity. First we prove a negative result that shows there does not exist a local graph trait which perfectly captures graph k-connectivity. We then present three different local graph traits which can be used to reliably predict the k-connectivity of a graph with varying degrees of accuracy. As a simple application of these results, we present upper and lower bounds for a local distributed algorithm which determines if a graph is k-connected. As a more elaborate application of local graph traits, we describe, and prove the correctness of, a local distributed algorithm that preserves k-connectivity in mobile ad hoc networks while allowing nodes to move independently whenever possible. 2011-04-29T17:44:11Z 2011-04-29T17:44:11Z 2010-12 Article http://purl.org/eprint/type/JournalArticle 3642176534 9783642176531 http://hdl.handle.net/1721.1/62568 Cornejo, Alejandro, and Nancy Lynch. “Reliably Detecting Connectivity Using Local Graph Traits.” Principles of Distributed Systems. (Lecture notes in computer science, v. 6490) Springer Berlin / Heidelberg, 2010. 87-102. Copyright © 2010, Springer https://orcid.org/0000-0003-3045-265X en_US http://dx.doi.org/10.1007/978-3-642-17653-1_8 Principles of distributed systems (Lecture notes in computer science, v. 6490) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer MIT web domain |
| spellingShingle | Cornejo Collado, Alex Lynch, Nancy Ann Reliably Detecting Connectivity Using Local Graph Traits |
| title | Reliably Detecting Connectivity Using Local Graph Traits |
| title_full | Reliably Detecting Connectivity Using Local Graph Traits |
| title_fullStr | Reliably Detecting Connectivity Using Local Graph Traits |
| title_full_unstemmed | Reliably Detecting Connectivity Using Local Graph Traits |
| title_short | Reliably Detecting Connectivity Using Local Graph Traits |
| title_sort | reliably detecting connectivity using local graph traits |
| url | http://hdl.handle.net/1721.1/62568 https://orcid.org/0000-0003-3045-265X |
| work_keys_str_mv | AT cornejocolladoalex reliablydetectingconnectivityusinglocalgraphtraits AT lynchnancyann reliablydetectingconnectivityusinglocalgraphtraits |