Consensus and collision detectors in wireless ad hoc networks
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37928 |
| _version_ | 1826208545267253248 |
|---|---|
| author | Newport, Calvin (Calvin Charles) |
| author2 | Nancy Lynch. |
| author_facet | Nancy Lynch. Newport, Calvin (Calvin Charles) |
| author_sort | Newport, Calvin (Calvin Charles) |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. |
| first_indexed | 2024-09-23T14:07:20Z |
| format | Thesis |
| id | mit-1721.1/37928 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:07:20Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/379282019-04-12T15:59:27Z Consensus and collision detectors in wireless ad hoc networks Newport, Calvin (Calvin Charles) Nancy Lynch. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006. Includes bibliographical references (p. 76-80). In this study, we consider the fault-tolerant consensus problem in wireless ad hoc networks with crashprone nodes. Specifically, we develop lower bounds and matching upper bounds for this problem in single-hop wireless networks, where all nodes are located within broadcast range of each other. In a novel break from existing work, we introduce a highly unpredictable communication model in which each node may lose an arbitrary subset of the messages sent by its neighbors during each round. We argue that this model better matches behavior observed in empirical studies of these networks. To cope with this communication unreliability we augment nodes with receiver-side collision detectors and present a new classification of these detectors in terms of accuracy and completeness. This classification is motivated by practical realities and allows us to determine, roughly speaking, how much collision detection capability is enough to solve the consensus problem efficiently in this setting. We consider ten different combinations of completeness and accuracy properties in total, determining for each whether consensus is solvable, and, if it is, a lower bound on the number of rounds required. (cont.) Furthermore, we distinguish anonymous and non-anonymous protocols-where "anonymous" implies that devices do not have unique identifiers-determining what effect (if any) this extra information has on the complexity of the problem. In all relevant cases, we provide matching upper bounds. Our contention is that the introduction of (possibly weak) receiver-side collision detection is an important approach to reliably solving problems in unreliable networks. Our results, derived in a realistic network model, provide important feedback to ad hoc network practitioners regarding what hardware (and low-layer software) collision detection capability is sufficient to facilitate the construction of reliable and fault-tolerant agreement protocols for use in real-world deployments. by Calvin Newport. S.M. 2007-07-18T13:12:04Z 2007-07-18T13:12:04Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37928 136931064 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 80 leaves application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Newport, Calvin (Calvin Charles) Consensus and collision detectors in wireless ad hoc networks |
| title | Consensus and collision detectors in wireless ad hoc networks |
| title_full | Consensus and collision detectors in wireless ad hoc networks |
| title_fullStr | Consensus and collision detectors in wireless ad hoc networks |
| title_full_unstemmed | Consensus and collision detectors in wireless ad hoc networks |
| title_short | Consensus and collision detectors in wireless ad hoc networks |
| title_sort | consensus and collision detectors in wireless ad hoc networks |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/37928 |
| work_keys_str_mv | AT newportcalvincalvincharles consensusandcollisiondetectorsinwirelessadhocnetworks |