Leader Election

Citizens in a democratic society usually vote to elect their leaders based on a pool of candidates. Distributed systems can choose a master node as well. Moreso , they can invoke “spot” elections in the situation of a leadership vacuum which helps in maintaining redundancy.

Introducing redundancy in services may introduce new problems of duplication and multi-operations. Leaders in a group of servers for redundancy will serve the business logic with the followers ready to take over leadership. Not a trivial problem with multiple systems that need to share state and gain consensus to elect the leader. Synchronization overhead and reduction of network trips are key considerations for this process.

Dealing with frameworks like Apache Spark on a daily basis makes you more aware of the inherent challenges stemming from a driver/worker architecture and the limited fault tolerance options when the master node goes down especially in high availability scenarios. Though several mitigation options exist (restarting with checkpoints, WALs etc)

As described here, Stable leader election ensures the leader remains that until any crashes irrespective of other behavior and its preferred they ensure minimal communication overhead, fault tolerant and ensure the leader is elected in constant time when the system is stable.

The Leader election process should guarantee that at most there is one leader at a time and eliminate the situation of multiple leaders being elected at the same time. This could be possible in network-partitioned systems where leaders being elected are unaware of each other. Zookeeper, Multi-paxos and Raft use temporary leaders to reduce number of messages required to reach an agreement.

Common Leader Election algorithms include the Bully algorithm or the Ring algorithm.


Bully Algorithm

Explained here

  • Each node gets a unique rank to help identify the leader
  • Elections begin when a node does not respond and the node that notices it first starts an election notifying the nodes greater than the fallen leaders rank.
  • The highest ranked responder takes over the process by responding to lower ranked nodes as well as a check to the fallen leader if any response.
  • If the node does not respond, there is a new leader elected.

This could be vulnerable to the multi-leader scenario if the nodes get split into different partitions. Also, the proclivity to the highest rank means unstable leaders can be elected which may mean frequent elections.

Here’s a quick barebones non-socket invocation of a 6-node election process.

Ring Algorithm

Explained here

  • Follows a ring topology and all nodes in the system form a ring
  • New election started when leader undergoes failure, with an alerting node notifying the next node on the ring.
  • Each node on the ring then contacts the next available node (higher ranked within the ring topology)
  • The node receives the responses back and confirms completeness of the traversal around the ring when it sees its own ID on the list and then picks the highest ID.

Apart from these, there are several other interesting implementations such as:

  • Next-in-line failover: Each elected leader provides a list of failover nodes and the leader failure starts a new election round.
  • Candidate/ordinary optimization: The nodes are split into candidate and ordinary – only one of the candidates can become a leader.
  • Invitation algorithm- Allows nodes to invite other nodes to join their groups instead of trying to outrank them

Alex Petrov’s book on Database Internals does a great job of explaining Election scenarios in a distribution context and has served as an inspiration for more detailed study in this topic.

Seven years

Seven years in Tibet by Heinrich Harrer

The author along with his friend, the resourceful Peter Aufschnaiter, takes you on a journey of 1000s of miles over hostile territories at a time of limited resources during the mid 20th century.  The first part of the book deals with the author’s numerous escapes and hardships that were overshadowed by his tenacity to get to the Tibetan capital, Lhasa◊We’ll sync on this next week internally for any options.

.Seven years in Tibet the tale of Austrian Mountaineer Heinrich Harrer’s trek through Tibet and his relationship with the 14th Dalai Lama. The Tibetan culture described before the Chinese invasion points to a simplistic life driven by a feudalistic society. I found the read immersive and had to pause many times to reflect back to a time that people today can never experience. The captivating descriptions of monks being carried on palanquins in Lhasa and the resplendent Potala Palace which was the home of the Dalai Lama leave a lasting impression.

The Dalai Lama , forbidden to mingle with the locals, would gaze from the Potala’s roof at Lhasa street life through a telescope and found a willing companion in the author who eventually rose to become the tutor regaling the young boy with his worldy experience. There are vivid descriptions on Tibetan rituals and the rustic but charming Tibetan way of life before the proceedings were rudely interrupted in 1950 by Mao Zedong’s invading army. The Dalai Lama’s flight to India from a chasing army was marked by the consecration of every building he stayed in during the journey as a holy place. That amazing journey is documented here.

The story ends at the foothills of the himalayas where the Dalai Lama still resides at the upper reaches of North India’s Kangra Valley in Dharamsala.

Harrer seems to be one hell of a renaissance man being a mountaineer, teacher, gardener, architect, civil servant and photographer besides being the part of the team that made the first ascent of the North Face of the Eiger in Switzerland. More importantly, he captures the times with his simplistic writing and takes the reader on a breathtaking journey. I found my self riveted by the journey more than the destination.

“One of the best characteristics of the Tibetan people is their complete tolerance of other creeds. Their monastic theocracy has never sought the conversion of infidels.”

Heinrich Harrer