Properties of link reversal algorithms for routing and leader election

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Radeva, Tsvetomira

Advisor dc:contributor.advisor

• Nancy Lynch.

• Electrical Engineering and Computer Science.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/82398

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/82398