Leader Election in Scala using Finagle for RPCs

In distributed systems, it is often of interest to find a distinguished node or process. For example, consensus algorithms like Raft has leader election as a step in maintaining a distributed and consistent log.

This post describes my prototyped implementation of the Hirschberg and Sinclair algorithm in Scala using Finagle for RPCs. This was done during hack week at Spotify to help me better understand distributed systems..

The actual implementation is far from being production ready, though I did learn some lessons in distributed computing, so thought I’d share some things I learned both on the theory and implementation side.

Hirschberg and Sinclair (HS) Algorithm

There are a few variations on what even constitutes a leader election algorithm. Should all nodes know who the leader is? Is there a specific topology of the nodes?The algorithm we implement does the following

Given a ring of nodes, have one node decide that it is the leader.

We assume that each node has a unique integer id associated with it, and the HS algorithm gives each node a set of instructions to determine if it is the leader. The leader, by definition, is the node with the largest id.

The difficulty is that each node will have the same set of instructions to determine if it is the leader, and we want to minimize the number of network calls for most nodes to realize they are not the leader and to guarantee that one node to realizes that it is the leader.

The algorithm is iterative, and proceeds as follows

(1) In the first stage, each node tells its two neighbors its Id.

If the node’s Id is larger than that of its neighbors, the neighbors pass that information back to the node so it can proceed to stage 2. Otherwise, the node knows it is not the leader and the node will break from the iterative algorithm.

(2) If a node proceeds to stage 2, it will send its Id outward to its 2nd order neighbors (its neighbors’ neighbors). If the Id of the original node is larger than the 2nd degree neighbors, the Id is sent back inward.

(3) The phase is increased until either the node realizes it is not the leader, or during the outgoing phase, the node compares it’s Id to itself and declares itself the leader.

This is visualized in the diagrams below. The first diagram shows what happens how node 42, which is not the leader, realizes that it is not the leader after phase 2 of the iterations.

Once node 17 passes info asking node 84 if node 42 is the leader, the process stops since 84 is larger than 42.

Let’s now see what happens for phases 1, 3 and 5 of how the node with Id 84 realizes it is the leader.

Implementation using Finagle

Finagle was a convenient choice for doing RPCs in Scala to quickly prototype the HS algorithm. The RPCs are done asynchronously, in contrast to usual textbook descriptions of the HS algorithm based on synchronous message passing. In the prototype, all “nodes” are independent processes on localhost, with different ports.

For the full code, check out the Github repo.