1047 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.
Leader Election should work with any topology and hence we take a look into an algorithm called FloodMax.
The Flood Max Algorithm Flood Max works with a network that is arbitrarily connected. It assumes that every node is given a comparable UID that may be randomly allotted and every node knows the network’s diameter.
The Flood Max algorithm is designed to elect the node with the maximum UID as the new leader and the core idea is to flood the network with the Max UID until the value converges.
The election process happens synchronously, which means every node moves forward in the algorithm in sync. There are ways to achieve this, but the implementation of synchronous behavior is out of the scope of this gist.
The algorithm stops after completing rounds equal to the diameter of the network. In each round, every node
After completing the
diameter number of rounds, each node will have the max UID it has seen so far which will also be the global maximum; thus every node will know who is the leader of the network.
It takes O(diameter) number of rounds to elect the leader and in each round the number of messages exchanged is equal to the number of edges, hence O(|E|); hence communication complexity is O(diameter x |E|).
To decrease the number of messages exchanged during the election, nodes can send the Max UID only when it changes. This would significantly reduce the messages exchanged across the network during leader elections.
Another optimization to reduce the communication is to NOT send the Max UID in the direction of the neighbor from which it was received.
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.