HS algorithm for Leader Election in Distributed Systems



527 views Distributed Systems



Leader Election is a critical component in any distributed system. It enables the system to auto-recover from leader failures. When a leader node goes down, the Leader Election algorithm is triggered to elect the new leader.

HS Algorithm

HS algorithm is synchronous which means every node proceeds with the algorithm in sync. A key highlight of this algorithm is that it has communication complexity i.e. number of messages exchanged, of O(n long).

The algorithm works with the following assumptions

  • every node has a comparable unique ID
  • the communication between nodes is bidirectional
  • the nodes are virtually arranged in a circular ring
  • the nodes know their immediate neighbors

The flow

Every node participates in the election. To pitch itself, it creates a message with its UID and sends it to its immediate neighbors in both directions.

To reduce the number of messages required to elect the new leader, the nodes who knows their UID is smaller, they quickly drop out of the election.

The election proceeds in phases. In each phase i, the nodes participating in the election send their candidature to a hop distance of 2^i and wait for it to come back.

Every node along the path, upon receiving the message,

  • if the incoming is greater than its own, it forwards it
  • if the incoming is lesser than its own, it discards

If the node, receives its UID as an incoming message from both directions then it knows that it has the maximum UID in the 2^i neighborhood. With each phase, the hop distance increases exponentially.

With each phase, the nodes with smaller UIDs start to drop off from the election while still acting as the transmitter of the messages. After certain phases, there will be only one node remaining and that becomes the new leader.

Halting

The leader election in the HS algorithm halts when the node receives its probe message and thus it knows that it is the only one left and hence declares itself as the new leader.

The new leader creates the announcement message and relays it across the ring announcing itself as the new leader all the nodes locally update it and the election is concluded.

Key Implementation Detail

The message sent across during the election contains <uid, hops, direction>. It helps the node know

  • the number of hops the message has taken
  • stop forwarding when the hop count becomes 0
  • in which direction to reply

Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 17000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Two Phase Commit to power Distributed Transactions in a Distributed System

618 views 28 likes 2022-09-16

Distributed Transactions are the heart and soul of Distributed Systems and getting all the participating nodes to agree ...

Exponential Information Gathering (EIG) Algorithm for Byzantine Agreement

379 views 16 likes 2022-09-14

Byzantine Agreement is an important problem to address in a Distributed Network. It is all about being tolerant of the n...

Exponential Information Gathering (EIG) Algorithm - Distributed Consensus even when processes crash

245 views 6 likes 2022-09-12

Exponential Algorithms have to be the worst possible way to solve Distributed Consensus; but are they really that bad? ...

FloodSet Algorithm - Distributed Consensus even when processes crash

432 views 14 likes 2022-09-09

Reaching a consensus is extremely critical in a Distributed System as we would have situations day-in and day-out where ...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

800+ learners

Details →

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.




Arpit's Newsletter read by 17000+ engineers

🔥 Thrice a week, in your inbox, an essay about system design, distributed systems, microservices, programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.



  • v12.7.8
  • © Arpit Bhayani, 2022

Powered by this tech stack.