## 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**^{2}) **Algorithm:**Consider N processes (P_{0}…..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.

- P
**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**^{2}) - 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)

- The number of messages required in a network of

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