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 for leader election is highly impractical, unbounded, yet an interesting algorithm to understand.
The algorithm assumes
nin the network
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.
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
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.
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.
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
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
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.
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.
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 ...
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...
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? ...
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 ...
A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.
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.
Powered by this tech stack.