An Asynchronous Leader Election Algorithm for Dynamic Networks
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
science projects buddy
Active In SP

Posts: 278
Joined: Dec 2010
28-12-2010, 11:38 PM

An Asynchronous Leader Election Algorithm for Dynamic Networks
B.Tech Seminar report
Sabitha C.B
Department of Computer Science And Engineering
Government Engineering College, Thrissur
December 2010

.pdf   An Asynchronous Leader Election Algorithm for Dynamic Networks.pdf (Size: 234 KB / Downloads: 60)

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

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 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 link reversal. In these algorithms, each node maintains a height variable,
drawn from a totally ordered set; the 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 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 link due to a 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.
Use Search at wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
Active In SP

Posts: 3
Joined: Oct 2009
07-08-2011, 08:51 PM

can u provide me the code ..........
seminar addict
Super Moderator

Posts: 6,592
Joined: Jul 2011
08-08-2011, 10:07 AM

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


Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Cut Detection in Wireless Sensor Networks pdf project girl 2 1,272 16-07-2015, 09:21 PM
Last Post: Guest
  computational intelligence in wireless sensor networks ppt jaseelati 0 369 10-01-2015, 03:10 PM
Last Post: jaseelati
  A Character Segmentation Algorithm for Printed Kannada Text Document uploader 1 1,508 10-01-2015, 12:52 PM
Last Post: zcfqmbrtb
  3D Steganography Algorithm project report helper 8 3,520 01-09-2014, 11:07 AM
Last Post: computer science crazy
  MANETS: MOBILE ADHOC NETWORKS seminar projects crazy 2 1,994 11-06-2014, 09:44 AM
Last Post: seminar project topic
  Towards Reliable Data Delivery for Highly Dynamic Mobile Ad Hoc Networks seminar ideas 11 3,979 02-04-2014, 12:50 PM
Last Post: Guest
  Bluetooth Based Smart Sensor Networks (Download Full Seminar Report) Computer Science Clay 91 69,007 04-03-2014, 12:46 AM
Last Post: nikhil goyal
  Vehicular Ad Hoc Networks (VANETs): Challenges and Perspectives seminar poster 0 478 29-10-2013, 01:40 PM
Last Post: seminar poster
  CLUSTERING IN WIRELESS SENSOR NETWORKS PPT project girl 1 1,209 14-10-2013, 09:30 AM
Last Post: Guest
  REPORT ON PID ALGORITHM VERIFICATION FOR DIFFERENT ERROR INPUT seminar projects maker 0 345 26-09-2013, 03:16 PM
Last Post: seminar projects maker