Repository logo
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Italiano
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
Repository logo
  • Communities & Collections
  • Research Outputs
  • Fundings & Projects
  • People
  • Statistics
  • English
  • Català
  • Čeština
  • Deutsch
  • Español
  • Français
  • Gàidhlig
  • Italiano
  • Latviešu
  • Magyar
  • Nederlands
  • Polski
  • Português
  • Português do Brasil
  • Suomi
  • Svenska
  • Türkçe
  • Қазақ
  • বাংলা
  • हिंदी
  • Ελληνικά
  • Yкраї́нська
  • Log In
    or
    New user? Click here to register.Have you forgotten your password?
  1. Home
  2. Indian Institute of Technology Madras
  3. Publication6
  4. Leader Election in Sparse Dynamic Networks with Churn
 
  • Details
Options

Leader Election in Sparse Dynamic Networks with Churn

Date Issued
01-11-2016
Author(s)
John Augustine 
Indian Institute of Technology, Madras
Kulkarni, Tejas
Sivasubramaniam, Sumathi
DOI
10.1080/15427951.2016.1199391
Abstract
We investigate the problem of electing a leader in a sparse but well-connected synchronous dynamic network in which up to a fraction of the nodes chosen adversarially can leave/join the network per time step. At this churn rate, all nodes in the network can be replaced by new nodes in a constant number of rounds. Moreover, the adversary can shield a fraction of the nodes (which may include the leader) by repeatedly churning their neighborhood and, thus, hindering, their communication with the rest of the network. However, empirical studies in peer-to-peer networks have shown that a significant fraction of the nodes are usually stable and well connected. It is, therefore, natural to take advantage of such stability to establish a leader that can maintain good communication with the rest of the nodes. Because the dynamics could change eventually, it is also essential to reelect a new leader whenever the current leader either has left the network or is not well-connected with rest of the nodes. In such reelections, care must be taken to avoid premature and spurious leader election resulting in more than one leader being present in the network at the same time. We assume a broadcast-based communication model in which each node can send up to O(log3n) bits per round and is unaware of its receivers a priori. We present a randomized algorithm that can, in O(log n) rounds, detect and reach consensus about the health of the leader (i.e., whether it is able to maintain good communication with rest of the network). In the event that the network decides that the leader’s ability to communicate is unhealthy, a new leader is reelected in a further O(log2n) rounds. Our running times hold with high probability provided a sufficiently large fraction of the nodes remain stable during the reelection process. Furthermore, we are guaranteed with high probability that there is at most one leader at any time.
Volume
12
Indian Institute of Technology Madras Knowledge Repository developed and maintained by the Library

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement
  • Send Feedback