TimeSlice algorithm for Leader Election in Distributed Systems

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

TimeSlice Algorithm

TimeSlice algorithm for leader election is highly impractical, unbounded, yet an interesting algorithm to understand.

The algorithm assumes

  • each node has a UID that is a positive integer
  • the nodes are arranged in a virtual ring
  • each node knows its immediate neighbor to the right
  • each node knows the total number of nodes n in the network

The flow

The election proceeds in phases 1, 2, 3, and so on. Each phase consists of n rounds. Because the algorithm is synchronous, each node knows when the algorithm is proceeding with rounds and phases.

In phase i, nodes can only forward the message having the candidature of UID i. Hence, in phase 3, a node will forward the message to the next node, only when it is having the candidature of UID 3.

The flow

In phase 1, the node with UID 1 will send the message with its candidature across to the next node in the ring. If no such node exists, then no message is sent.

Thus, for n rounds within phase 1 there is void silence in the network. Then beings the phase 2.

Hence, we see that the messages will be sent across the ring only when the phase i beings where i is the smallest UID in the network. For all (i - i) * n rounds, there will be void silence in the network.

When phase i begins the node with UID i will know that it is the new leader and it initiates the message and sends it to the next neighbor. For n successive rounds, the message is sent across the network and thus all n nodes know about the new leader i.

Complexity Analysis

The algorithm thus elects the node with the minimum UID as the new leader in just O(n) messages but takes time proportional to the O(n*i).

If the minimum UID is a large integer, then the algorithm will take a longer time to elect the leader, and hence it is unbounded on the number of nodes in the network.

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.