5: Leader Elections

Synchronous Network Model

A directed graph, often representing nodes in a system, where messages can be exchanged with each other.

• G = (V, E) with a fixed alphabet M

Distance

The shortest path between two nodes is the length of the shortest path between those two nodes.

Distance of a Graph

The maximum distance between any two nodes.

Synchronous Network Model - Node Contents

• states_i - set of states

• start_i - starting states

• messages_i - message generation function

• trans_i - state transition functions mapping states_i and vectors

Synchronous Network Model - Edge (Channel) Contents

Either nothing, or a single message M.

Synchronous Network Model - Process

• All processes (nodes) begin in arbitrary start states

• All channels (edges) are empty

• Processes repeat continually:

  • Apply message-generation function to current state to generate a message sent to all outgoing neighbours

  • Messages are put in appropriate channels

  • Apply the state-transformation function to the current state and incoming messages to obtain the new state

  • Remove all messages from channels

Synchronous Network Model - What Can Go Wrong

• Link failure - channel loses messages

• Stop failure - process stops mid-execution

• Byzantine failure - an arbitrary message/state is generated that doesn’t follow the rules of the message generation/state transition functions

Leader Election Problem

The problem of choosing a “leader” node in a network and holding the data necessary for the function.

Leader Election Problem - Variations

• Unidirectional/Bidirectional Path

• Number of processes may be known or unknown

• Non-leaders may be required to acknowledge that they are not the leader

• Unique IDs may be consecutive integers or not

• Unique IDs may admit operations other than comparison

Leader Election Problem - Safety Specification

There is at most one leader in the system.

Leader Election Problem - Liveness Specification

Sometimes, there exists a leader (either no correct node exists or a node is eventually elected leader).

Leader Election Problem - Problem Modelling (Token Ring Network)

• Network is a connected ring

• Nodes have consecutive unique identifiers

• Synchronous model

• Each node knows its right and left neighbour

• Addition is module-N

• Unidirectional ring of unknown size

LCR Algorithm

A solution to the Leader Election Problem by electing the process with the highest identifier.

LCR Algorithm - Process

• A process notes a lack of leader and initiates an election.

• It creates an election message and passes it to neighbouring nodes.

• When a node receives an election message:

  • The receiving UID is checked against its own UID

  • If the receiving UID is bigger, then the node continues passing the original election message

  • If the receiving UID is smaller, then the node passes on a new election message containing its own UID.

  • The node becomes a candidate.

• If a candidate receives an election message:

  • If the UID is its own, then it is the leader.

  • If its UID is not its own, then the election is lost.

• The leader sends a message across the network informing other nodes it has been elected.

LCR Algorithm - Liveness

A process i_max outputs a leader by the end of round n.

• We know u_max is the initial value of u_imax by initialisation

• The values of u never change and are distinct by assumption

• i_max has the largest u value by definition of i_max

• Suffices to show that after n rounds, status_imax = leader

LCR Algorithm - Safety

No process other than i_max ever outputs the value leader.

• All other processes always have the status = unknown

LCR Algorithm - Message Complexity

O(n²)

• n rounds before a leader is elected

LCR Algorithm - Halting

All processes never reach a halting state.

• We can add a “finished” message initiated by the elected leader.

• 2n rounds before a leader is elected, but message complexity remains the same

Hirschberg and Sinclair (HS)

A solution to the Leader Election Problem by sending a token in each direction before returning back to the origin node.

Hirschberg and Sinclair (HS) - Process

• Each process, i, operates in a phase, e.g. 0, 1, 2…

• In phase l, process i sends out “tokens” containing its identifier u_i in each direction

• Intended to have travel distance 2^l before returning back to i

• If both tokens make it back safely, then process i continues the following phase

• Whilst u_i is proceeding in the outbound direction, each other process j on the path compares u_i with its own identifier, u_j

  • If u_i < u_j then j discards the token and returns its own

  • If u_i > u_j then j relays u_i

  • If u_i = u_j, then process j has received its own identifier before the token has turned around, so it elects itself leader

Hirschberg and Sinclair (HS) - Message Format

<id, direction, hop_count>

Hirschberg and Sinclair (HS) - Individual State Contents

• u, a unique ID

• send+, containing either an element of M or null

• send-, containing either an element of M or null

• status, {unknown, leader} (initially unknown)

• phase, non-negative int (initially zero)

• message generation function:

  • Send the current value of send to process i + 1

  • Send the current value of send to process i - 1