[attachment=7711]

Abstract
This is a leader election algorithm, used in dynamic networks. In this algorithm
what pattern of topology change occur, when the topology change is over then every
connected component in the network will contain a unique leader. Dynamic network
is a network whose communication topology changes frequently. This algorithm is
applicable in asynchronous networks. The algorithm is developed using ideas from a
routing algorithm named TORA. TORA (Temporally Ordered Routing Algorithm)
is a routing algorithm for mobile ad hoc networks. TORA uses a Wave algorithm
and a height-based mechanism for reversing the logical direction of communication
links [6]. In this algorithm if a node loses its last outgoing page link it will start search
for the leader, if it cannot get a path to the leader it will elect itself as a leader. If
it finds the old leader there will not be any change in the leader. This algorithm can
elect any node as the leader, involves fewer types of messages than other algorithms,
and uses point-to-point communication rather than broadcasting. The strategy for
breaking ties between competing leaders makes this algorithm compact and elegant,
as messages sent between nodes carry only the height information of the sending node,
and every message is identical in content. This algorithm is also suited to an arbitrary
communication topology. It is proved that in certain well-behaved situations, a new
leader is not elected unnecessarily.

Chapter 1
Introduction
Leader election is important in distributed computing, it is used as a subroutine
for any application that requires the selection of a unique processor among multiple
candidate processors. Applications that need a leader range from the primary-backup
approach to replication based fault-tolerance to group communication systems , and
from video conferencing to multi-player games . A core activity for a network leader
is communication. Clear and transparent communication around the networks aims,
values and activities are crucial to building ownership and participation. A network
needs data, information and intelligence around which to plan, work and learn. A network
leader will be proactive in identifying and accessing knowledge sources within
and beyond the network. A network leader brokers and sustains the relationships,
carefully building trust and security as a foundation for innovation and experimentation.
In a dynamic network, communication links go up and down frequently. Wireless
mobile networks are one example of dynamic networks, since node mobility changes
the communication topology continuously. Even if nodes do not move, wireless communications
are subject to more interference than in the wired case, but wired networks
can also experience frequent topology changes. Recent research has focused
on porting some of the applications mentioned above to dynamic networks, including
wireless and sensor networks. For instance, Wang and Wu propose a replication-based
scheme for data delivery in mobile and fault-prone sensor networks . Thus there is a
need for leader election algorithms that work in dynamic networks.
This algorithm consider the problem as the one which ensures that, if page link changes
eventually cease, then eventually each connected component of the network has a
unique leader, this is represented as the local leader election problem[3]. The algorithm
is presented as an extension of the leader election algorithm in, which in turn is
an extension of the MANET routing algorithm TORA[10]. TORA itself is based on
ideas from two routing algorithms presented by Gafni and Bertsekas [4]based on the notion of page link reversal. In these algorithms, each node maintains a height variable,
drawn from a totally ordered set; the page link between two nodes is considered to be
directed from the endpoint with larger height to that with smaller height. Whenever
a node becomes a sink, i.e., has no outgoing links, due to a page link failure or due to
notification of a neighbors changed height, the node increases its height so that at
least one of its incoming links becomes outgoing. In one of the algorithms, the height
is a pair, while in the other the height is a triple; in both situations, heights are
compared lexicographically and the least significant component is the nodes unique
id. The algorithms cause an infinite number of messages to be sent if a portion of the
graph is disconnected from the destination.
This drawback is overcome in TORA, through the addition of a clever mechanism
by which nodes can identify that they have been partitioned from the destination. In
this case, the nodes go into a quiescent state. In TORA, each node maintains a 5-tuple
of integers for its height, consisting of, from left to right, a 3-tuple called the reference
level, a delta component, and the nodes unique id. The height tuple of each node is
lexicographically compared to the tuple of each neighbor to impose a logical direction
on links (higher tuple toward lower.) The purpose of a non-zero reference level is to
indicate when nodes have lost their path to the destination. Initially, the reference
level is all zeroes. When a node loses its last outgoing page link due to a page link disappearing,
it starts a new reference level by changing the first component of the triple to the
current time, the second to its own id, and the third to 0, meaning that the search for
the destination is started. Reference levels are propagated throughout a connected
component, as nodes lose outgoing links, in a search for an alternate directed path to
the destination. Propagation of reference levels is done using a mechanism by which a
node increases its reference level when it becomes a sink; the delta value of the height
is manipulated to ensure that links are oriented appropriately. If one section of the
communication graph is a dead-end, then the third component of the reference level
triple is set to 1. When this happens, the reference level is said to have been reflected,
since it is subsequently propagated back toward the originator. If the originator receives
reflected reference levels back from all its neighbors, then it has identified a
partitioning from the destination.
The key observation in a Leader election algorithms for mobile ad hoc networks
presented by N. Mopani, J. Welch, and N. Vaidya[6] is that TORA can be adapted for
leader election: when a node detects that it has been partitioned from the destination
(the old leader), then, instead of becoming quiescent, it elects itself. The information
about the new leader is then propagated through the connected component. A sixth
component was added to the height tuple to record the leaders id.
However, when multiple topology changes occur, this algorithm can fail. But this new algorithm works in an asynchronous system with arbitrary topology changes.
One new feature of this algorithm is to add a seventh component to the height: a
timestamp associated with the leader id that record the time that the leader was
elected. This algorithm also includes a new rule by which nodes can choose new leaders.
A newly elected leader initiates a wave algorithm[9]: when different leader ids
collide at a node, the one with the most recent timestamp is chosen as the winner
and the newly adopted height is further propagated. This strategy for breaking ties
between competing leaders makes our algorithm compact and elegant, as messages
sent between nodes carry only the height information of the sending node and every
message is identical in content.

can u provide me the code ..........

To get more information about the topic " An Asynchronous Leader Election Algorithm for Dynamic Networks" please refer the page link below

http://studentbank.in/report-an-asynchro...8#pid53838