HS Protocol

The nodes are in a ring. Every node has a UID \(u\). 

Initialize:
  uid           // the unique ID of this process
  active := true
  status := null
  phase := 0

// The algorithm proceeds until a leader is chosen
while status = null do
  if active then
    forward_msg := (uid, distance = 2^phase, direction = forward)
    backward_msg := (uid, distance = 2^phase, direction = backward)
  else
    forward_msg := null
    backward_msg := null

  // ---------------------
  // Forward direction phase
  // ---------------------
  for step in 1 to 2^phase do
    // Send forward_msg to successor (u+1)
    send forward_msg to (u+1)
    // Receive a forward-traveling message from predecessor (u-1)
    forward_in := receive from (u-1)

    if forward_in != null then
      let (f_id, f_dist, f_dir) = forward_in
      if f_id > uid then
        // Found a larger ID
        active := false
      else
        // f_id <= uid
        f_dist := f_dist - 1
        if f_dist = 0 then
          // The message completed its intended distance
          if f_id = uid and active
            // Got our own ID back without interruption
            // This direction is "cleared" (no larger found)
            forward_msg := null
          else
            // If not our ID or we are inactive, discard
            forward_msg := null
        else
          // Continue forwarding smaller ID
          forward_msg := (f_id, f_dist, f_dir)
    else
      // No incoming message means no forwarding needed
      forward_msg := null

  // ---------------------
  // Backward direction phase
  // ---------------------
  for step in 1 to 2^phase do
    // Send backward_msg to predecessor (u-1)
    send backward_msg to (u-1)
    // Receive a backward-traveling message from successor (u+1)
    backward_in := receive from (u+1)

    if backward_in != null then
      let (b_id, b_dist, b_dir) = backward_in
      if b_id > uid then
        // Found a larger ID
        active := false
      else
        // b_id <= uid
        b_dist := b_dist - 1
        if b_dist = 0 then
          // The message completed its intended distance
          if b_id = uid and active
            // Got our own ID back without interruption
            backward_msg := null
          else
            backward_msg := null
        else
          backward_msg := (b_id, b_dist, b_dir)
    else
      backward_msg := null

  // ---------------------
  // End of phase checks
  // ---------------------
  if active and forward_msg = null and backward_msg = null then
    // No larger ID found this phase. We continue unless we detect a global stop.
    // If at any point we discover we are the only active process, we become leader.
    // (This detection can be via additional logic or known termination conditions.)
    if "no other active process" detected then
      status := leader
    else
      phase := phase + 1
  else
    // We encountered a larger ID or are waiting for another phase.
    if not active
      // We remain inactive and just pass messages for others in future phases.
      phase := phase + 1
    else
      // If still active but haven't confirmed leadership, proceed to next phase
      phase := phase + 1

Example

Below is a step-by-step example to illustrate how the Hirschberg–Sinclair (HS) algorithm works in practice. Consider a small ring and let us walk through a few phases to see how processes drop out until only the leader (the node with the largest ID) remains.

Setup:

Suppose we have a ring of \(8\) processes arranged in a circle:

P0 → P1 → P2 → P3 → P4 → P5 → P6 → P7 → (back to P0)

Each process has a unique identifier (ID). Let’s assign them as follows:

P0: ID = 3 P1: ID = 5 P2: ID = 10 P3: ID = 2 P4: ID = 9 P5: ID = 8 P6: ID = 4 P7: ID = 7

Thus, the ring with IDs is:

P0(3) P7(7) P1(5) P6(4) P2(10) P5(8) P3(2) P4(9)

Initially, all processes are active candidates.

Overview of the Algorithm’s Structure:

The HS algorithm runs in phases \(i = 0,1,2,\ldots\). In each phase \(i\):

  • Each active process sends out "challenge" messages with its ID up to \(2^{i}\) hops in both directions.
  • If a process with a smaller ID encounters a larger ID within that radius, it learns that it cannot be the leader and becomes inactive.
  • As phases progress, the distance doubles, but fewer processes remain active.

Eventually, after \(O(\log{n})\) phases, only the largest ID process remains active and declares itself the leader.

Phase 0 (i = 0)

Distance: \(2^0=1\) hop.

Every active process (which is all of them at this point) sends a challenge message containing its ID one hop in both directions.

  • P0(3) sends its ID (3) to P7 and P1.
  • P1(5) sends its ID (5) to P0 and P2.
  • P2(10) sends its ID (10) to P1 and P3.
  • P3(2) sends its ID (2) to P2 and P4.
  • P4(9) sends its ID (9) to P3 and P5.
  • P5(8) sends its ID (8) to P4 and P6.
  • P6(4) sends its ID (4) to P5 and P7.
  • P7(7) sends its ID (7) to P6 and P0.

What happens at each receiver?

  • When P7 receives ID(3) from P0, it compares 3 to its own ID(7). Since 7 > 3, P7 knows there is a smaller contender (3) behind it, but P7 doesn’t drop out for that reason. Instead, P0 might realize it has encountered someone bigger. Similarly, P1 sees ID(3) from P0 and compares 3 < 5, so P1 is bigger than P0.
  • More importantly, each challenge message that moves outward checks if it encounters a bigger ID. At the end of this step, each process looks at what messages it sent and what “larger IDs” it learned of.

Let’s consider one process at a time:

  • P0(3):
    • P0 sent ID(3) to P1 and P7.
    • P1 has ID(5), which is greater than 3. Thus, P0 learns there is a process with ID(5) nearby.
    • Similarly, P7 has ID(7), which is also greater than 3.
    • Conclusion: P0 finds two processes in its immediate neighborhood larger than itself. P0 becomes inactive.
  • P1(5):
    • P1 sent ID(5) to P0(3) and P2(10).
    • P2(10) is greater than 5, so P1 discovers a larger ID to one side.
    • Therefore, P1 becomes inactive.
  • P2(10):
    • P2 sent ID(10) to P1(5) and P3(2).
    • Both neighbors have smaller IDs (5 and 2), so P2 sees no one larger within 1 hop.
    • P2 remains active (so far it’s the “king of the hill” in its immediate area).
  • P3(2):
    • Sent ID(2) to P2(10) and P4(9).
    • P2(10) and P4(9) are both larger than 2.
    • P3 becomes inactive.
  • P4(9):
    • Sent ID(9) to P3(2) and P5(8).
    • P3(2) is smaller, P5(8) is smaller. No larger ID found.
    • P4 stays active.
  • P5(8):
    • Sent ID(8) to P4(9) and P6(4).
    • P4(9) is larger than 8.
    • P5 becomes inactive.
  • P6(4):
    • Sent ID(4) to P5(8) and P7(7).
    • P5(8) is larger than 4 and P7(7) is also larger.
    • P6 becomes inactive.
  • P7(7):
    • Sent ID(7) to P6(4) and P0(3).
    • Both 4 and 3 are smaller than 7, so P7 sees no larger ID within 1 hop.
    • P7 remains active.
  • Result after Phase 0:
    • Active: P2(10), P4(9), P7(7)
    • Inactive: P0(3), P1(5), P3(2), P5(8), P6(4)

Phase 1 (i = 1)

Distance: \(2^1=2\) hops.

Now only P2, P4, and P7 are active. They will send out their IDs 2 hops in both directions.

Consider each active node:

  • P2(10):
    • Two hops clockwise: P2 → P3 → P4. Encounters P3(2) and then P4(9). Among these, P4(9) is large but still smaller than 10.
    • Two hops counterclockwise: P2 → P1 → P0. Encounters IDs 5 and 3, both smaller than 10.
    • No larger ID found. P2 remains active.
  • P4(9):
    • Two hops clockwise: P4 → P5 → P6. Encounters IDs 8 and 4, both smaller than 9.
    • Two hops counterclockwise: P4 → P3 → P2. Encounters ID 2 and then ID 10. Uh-oh, P4 finds a larger ID (10) at P2.
    • P4 discovers that there’s a bigger contender (P2) within 2 hops. P4 becomes inactive.
  • P7(7):
    • Two hops clockwise: P7 → P0 → P1. Encounters IDs 3 and 5, both smaller than 7.
    • Two hops counterclockwise: P7 → P6 → P5. Encounters IDs 4 and 8. Here, 8 is actually larger than 7. But wait, P5 was marked inactive at the end of the last phase. Even though P5 is inactive, it still has ID=8, which is known to be larger than 7. Generally, an inactive node will forward messages, but the key point is that P7 sees a node with a bigger ID in the path. Let’s assume the algorithm’s variant we’re using stops the challenge once a bigger ID is discovered or that P7 eventually learns about P5’s larger ID from the returned messages.
    • P7 discovers that ID=8 is larger than 7, so P7 becomes inactive.
  • Result after Phase 1:
    • Active: P2(10)
    • Inactive: P0(3), P1(5), P3(2), P4(9), P5(8), P6(4), P7(7)

    Now only P2 with ID=10 remains active.

Phase 2 (and beyond)

By the start of Phase 2, there is only one active process left: P2(10). Since no other processes are active, P2 automatically becomes the leader. The algorithm typically checks a few more phases or has a termination condition, but effectively, no one will challenge P2 anymore, and P2 knows it’s the largest remaining contender.

Final Outcome:

P2 (with ID = 10) is the leader.

Notes

  • This is from Distributed algorithms. Nancy A. Lynch. 1997
  • This is also called the HS algorithm (Hirschberg and Sinclair).
  • The round complexity is \(O(n\log{n})\).
  • The communication complexity is \(O(n\log{n})\).
  • It also works if the nodes do not start at the same time.