Hajussüsteemid 2020/21 kevad

Seminar 7: Election Algorithms

Goal:

• To understand the concept behind Election Algorithms.
• Learn how to apply election algorithm by bullying to a system of processes

Description: In Election algorithms, We require some Processes to act as a Coordinator. The main issue here is to how to select this Coordinator dynamically.

Basic Assumptions:

• All processes have unique id’s
• All processes know id’s of all processes in the system (but not if they are up or down)
• Election means identifying the most suitable process based on different factors, e.g., highest id

Definitions

• In Election Algorithms, one process needs to act as a coordinator.
• The technique or algorithm here is to pick up a Unique Coordinator.
• The need to choose a Unique Coordinator arises in case of a failed process or when we need to pick a master in Berkeley Clock Synchronization Algorithm.
• Types of Election Algorithm:
  • Bully Algorithm
  • Ring Algorithm
• Bully Algorithm:
  • Each process has a Unique Numerical ID.
  • Processes know the ID's and address of every other process.
  • Communication is assumed to be reliable.
  • The key idea as mentioned earlier is to select process with highest ID.
  • Process initiates election if it just recovered from failure or if coordinator has just failed.
  • Several Processes can initiate an election simultaneously.
  • The messages required to be sent with n Processes is of the order of O(n²)
  • Algorithm: Consider N processes (P₀ …..P_{N -1}) and let id(P_K) = k. When a process P_K notices that the coordinator is no longer responding to requests, it initiates an election:
    • P_K sends an ELECTION message to all processes with higher identifiers: P_K+1, P_K+2 ..... P_N-1
    • If no one responds, P_K wins the election and becomes coordinator.
    • If one of the higher-ups answers, it takes over and P_K's job is done.
  • Algorithm Explained: Suppose Process P sends a message to the coordinator:
    • If Coordinator does not respond to the request within a time interval T, then it is assumed that the coordinator has failed.
    • Now Process P sends election message to every process with high priority number.
    • It waits for response, if no process responds in time interval T, then process P elects itself as Coordinator.
    • Then it sends a message to all lower priority numbers that it is elected as their new coordinator.
    • However, if an answer is received within time T from any other process Q:
      • Process P again waits for time interval T to receive another message from Q that it has been elected as Coordinator.
      • If Q doesn't respond within time interval T, Then it is assumed to have failed and the algorithm is restarted. For Example:

In the above example, Process 7 which was the Coordinator fails. Process P4 starts an election and a total of 15 messages are required to elect a new coordinator. The number of messages required depends on which Process initiates the election:

• If Process 0 starts an election, maximum number of messages will be required to elect a new coordinator (Worst Case).
• If Process 6 initiates an election, minimum number of messages will be required to elect a new coordinator (Best Case).

EXERCISE: The figure shows 6 processes where process 6 is the coordinator, as it has the highest ID. Assume Process 6 fails, resolve using bullying algorithm and answer the following:

• What is the number of messages required to elect a new coordinator, if:
  • Process 1 initiates an election (Worst Case)
  • Process 2 initiates an election
  • Process 3 initiates an election
  • Process 4 initiates an election
  • Process 5 initiates an election (Best Case)
• Generalise a formula that estimates the number of messages required in a network of N processes to select a new coordinator in worst case scenario.
  • Hint:
    • The number of messages required in a network of N Processes is of the order of O(N²)
    • Derive a formula for the number of messages sent in worst case. In such as case, Process with the lowest ID initiates an election and sends N-1 messages and receives N-2 replies. After that, every i-th process (for i = 1,2,3 ...... N-1) will send N-i messages and receive N-i-1 replies. Finally, the (N-1) process wins and sends N-2 Coordinator messages
    • So f(N) = N - 1 + N - 2 + ({$\sum\limits_{i=2}^{N-1}$} (N - i) + (N - i - 1)) + N - 2
    • Now Solve (Apply Arithmetic Sum Rule)

Deliverables of practical session: A PDF file containing the answers to above exercise.