Arpit's Newsletter read by 38000+ 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
Super practical courses, with a no-nonsense approach, are designed to spark engineering curiosity and help you ace your career.
System Design for Beginners
An in-depth, self-paced, and on-demand course that for early engineers to become great at designing scalable, available, and extensible systems at scale.
System Design Masterclass
A masterclass that helps experienced engineers become great at designing scalable, fault-tolerant, and highly available systems.
Redis Internals
A course that helps covers Redis internals by reimplementing its core features like - event loop, serialization protocol, pipelining, eviction, and transactions.