Properties of link reversal algorithms for routing and leader election
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/82398 |
| _version_ | 1826211629508853760 |
|---|---|
| author | Radeva, Tsvetomira |
| author2 | Nancy Lynch. |
| author_facet | Nancy Lynch. Radeva, Tsvetomira |
| author_sort | Radeva, Tsvetomira |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013. |
| first_indexed | 2024-09-23T15:09:01Z |
| format | Thesis |
| id | mit-1721.1/82398 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:09:01Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/823982019-04-11T11:19:33Z Properties of link reversal algorithms for routing and leader election Radeva, Tsvetomira Nancy Lynch. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department 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, 2013. Cataloged from PDF version of thesis. Includes bibliographical references (p. 75-77). We present two link-reversal algorithms and some interesting properties that they satisfy. First, we describe the Partial Reversal (PR) algorithm [13], which ensures that the underlying graph structure is destination-oriented and acyclic. These properties of PR make it useful in routing protocols and algorithms for solving leader election and mutual exclusion. While proofs exist to establish the acyclicity property of PR, they rely on assigning labels to either the nodes or the edges in the graph. In this work we present simpler direct proof of the acyclicity property of partial reversal without using any external or dynamic labeling mechanisms. Second, we describe the leader election (LE) algorithm of [16], which guarantees that a unique leader is elected in an asynchronous network with a dynamically-changing communication topology. The algorithm ensures that, no matter what pattern of topology changes occurs, if topology changes cease, then eventually every connected component contains a unique leader and all nodes have directed paths to that leader. Our contribution includes a complexity analysis of the algorithm showing that after topology changes stop, no more than 0(n) elections occur in the system. We also provide a discussion on certain situations in which a new leader is elected (unnecessarily) when there is already another leader in the same connected component. Finally, we show how the LE algorithm can be augmented in such a way that nodes also have the shortest path to the leader. by Tsvetomira Radeva S.M. 2013-11-18T19:18:13Z 2013-11-18T19:18:13Z 2013 2013 Thesis http://hdl.handle.net/1721.1/82398 862110423 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 77 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Radeva, Tsvetomira Properties of link reversal algorithms for routing and leader election |
| title | Properties of link reversal algorithms for routing and leader election |
| title_full | Properties of link reversal algorithms for routing and leader election |
| title_fullStr | Properties of link reversal algorithms for routing and leader election |
| title_full_unstemmed | Properties of link reversal algorithms for routing and leader election |
| title_short | Properties of link reversal algorithms for routing and leader election |
| title_sort | properties of link reversal algorithms for routing and leader election |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/82398 |
| work_keys_str_mv | AT radevatsvetomira propertiesoflinkreversalalgorithmsforroutingandleaderelection |