Seminar 6: The Ring Algorithm in python
Goal: To study and practice the concept of election algorithm (The Ring Algorithm)
Background: Election algorithms choose a process/node from group of (candidate) processors/nodes to act as a coordinator. If the coordinator process crashes due to some issues, then a new coordinator is elected from the remaining candidates. Election algorithm is helpful to elect the leader in a safety manner.
- So how do we elect the leader?
Leader election consists of giving one process/node in a distributed system some special powers. Those special powers include the ability to assign work, the ability to modify a piece of data, or even the responsibility of handling all requests in the system
- When selecting a leader/coordinator, two properties need to be guaranteed:
- Safety: There is at most one leader at any given time.
- Liveness: The election eventually is completed
- Model Assumptions:
- Each process has a unique number
- One process per machine
- Processes know each other’s process number
- Processes do not know the status of the other processes, i.e. up or down
- In general, the process with the highest ID number will be the new coordinator
The Ring Algorithm
- In distributed computing, the ring algorithm assumes that the processes are arranged in a logical ring and each process knows the order of the ring of processes (unidirectional). All messages are sent clockwise around the ring.
- Faulty processes are those that don’t respond in a fixed amount of time
- Even if two ELECTIONS started at once, everyone will pick same leader since the node with highest identifier is picked
- Messages go around the ring till they return to the initiator
Implementation
- When a process notices that current leader failed:
- Sends an ELECTION message to start the algorithm to its successor; It contains its own id. (if successor is down, sender skips until a running process is located).
- When a process receives an ELECTION message:
- process adds its own id to the list and sends to successor.
- When ELECTION message gets back to the initiator (process recognizes the message that contains its own id):
- Sends a LEADER message that announces the new leader and contains: id of new leader (list member with highest number); List of the members of the new ring. Message circulates around the ring.
- When the LEADER message gets back to initiator:
- Election is over if id of new leader is in ring id-list.
- Else the algorithm is repeated (handles election failure).
Example of the ring algorithm handling failure
Here is a screen shot illustrating the initial part of this example. Using this code for implementation. (Code)
- Running ring2.py
Exercise: We will get acquainted with the Ring algorithm using gRPC with 3 processes in a local host and select a leader with process ID 3 initiating the election. The result will look like these screenshots. (Here I only defined the process number and not the list of processes)
- Implementing the server.py
- Implementing the client.py
Task: From previous seminars, we already understand how to implement some functions with multi-threads by using gRPC. For this task, integrate the Ring algorithm into a unique function to show different processes (4 or more).
- Initiate an election process with any of the processes and determine the leader or coordinator
- Also include any time synchronization algorithm to your implementation
Deliverables: For the task, please contain the source python file, and also the screenshot of results in terminals. Then put all the file in a single zip.
Relative Links