Arpit's Newsletter read by 90000+ engineers
Weekly essays on real-world system design, distributed systems, or a deep dive into some super-clever algorithm.
TimeSlice algorithm for Leader Election in 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
nin 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.
Here's the video ⤵
Courses I teach
Alongside my daily work, I also teach some highly practical courses, with a no-fluff no-nonsense approach, that are designed to spark engineering curiosity and help you ace your career.
System Design Masterclass
A no-fluff masterclass that helps experienced engineers form the right intuition to design and implement highly scalable, fault-tolerant, extensible, and available systems.
System Design for Beginners
An in-depth and self-paced course for absolute beginners to become great at designing and implementing scalable, available, and extensible systems.
Redis Internals
A self-paced and hands-on course covering Redis internals - data structures, algorithms, and some core features by re-implementing them in Go.