Seminar 6: Bullying Algorithm in python
Goal: To study and practice the concept of election algorithms (The Bully Algorithm)
Background: Leader election consists in 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.
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.
- Basic assumptions:
- All processes/nodes have unique id
- All processes/nodes know id of all processes in the system (but not if they are down)
- Election means identifying the most suitable process based on different factors, e.g., highest id.
Bullying Algorithm
- In distributed computing, the bully algorithm is a method for dynamically electing a coordinator or leader from a group of distributed computer processes. The process with the highest process ID number from amongst the non-failed processes is selected as the coordinator.
- Implementation: Consider N processes (P0 …..PN -1) and let id(PK) = k. When a process PK notices that the coordinator is no longer responding to requests, it initiates an election:
- PK sends an ELECTION message to all processes with higher identifiers: PK+1, PK+2 ..... PN-1
- If no one responds, PK wins the election and becomes coordinator.
- If one of the higher-ups answers, it takes over and PK's job is done.
- Example: Suppose Process P4 sends a message to the coordinator P7:
- If Coordinator P7 does not respond to the request within a time interval T, then it is assumed that the coordinator has failed.
- Now process P4 sends Election message to every process with higher numbers 5, 6 and 7.
- P4 waits for response, if no process responds in time interval T, process P4 elects itself as Coordinator. Then P4 sends COORDINATOR message to all lower priority numbers (0, 1, 2 and 3) that it is elected as their new coordinator.
- However, if P4 receives the answer within time T from any other process Q (5 and 6), then the process Q restart the election until the process P6 wins and becomes the new coordinator by sending COORDINATOR message to all lower priority numbers.
- If Q doesn't respond within time interval T, then it is assumed to have failed and the algorithm is restarted.
- If process 7 is restarted, it will send COORDINATOR message to others and bully them into submission
- When P4 start the election and P6 wins the coordinator, 15 messages are passed.
Task-1: In Seminar 4, we have learnt how to implement Berkeley Algorithm for clock synchronization based on the pre-assigned and fixed coordinator. In this similar, you should achieve the Bully Algorithm based on clock-sync.py to select the coordinator dynamically. The code for the above implementation is given here for you. (code)
- The input file for Bully Algorithm is bully.txt
- 1, A_K, 11:00 --> process_ID, process_NAME, process_TIME
- Process(p[0], p[1], p[2]) --> 3 parameters
- Define a bully function to select the coordinator based on the highest ID.
- As the update-clock function defined before (in seminar 4) runs automatically, the bully function can be invoked in the update-clock function for dynamic coordinator selection (also running automatically) when one coordinator fails. This ensures that the clock of other processes is in sync with the new coordinator when you input the command clock.
- Define a kill function to remove a process（including coordinator）
- If the coordinator is removed, clocks are reset to their original time (the one defined in the bully.txt), and a new election needs to happen automatically (bully function). The program should notify the process that is the new coordinator and clocks of all the processes are synchronized based on the clock of the new coordinator.
- Note that when the coordinator is killed, the timer can continue from the previously counted time, for example if the coordinator is killed after running 40 seconds, the original time of a new coordinator is 15:00 and it can continue counting from 15:40. The new coordinator can also start from begining 15:00. Both implementations are good.
- The result should be similar to this.
Task-2: In Seminar 4, we already practice to implement Berkeley algorithm by using RPyC ThreadedServer in python. For this task:
- integrate the bully function of Task-1 into RPyC server communiction.
- pass arguments one by one ("bully.txt" and different commands) from client to server.
- The Result should be similar to this.
Deliverables: For each task, please contain the source python file, and also the screenshot of results in terminals. Then put all the file in a single zip.
- If you have different solutions for the tasks, please submit all your solutions with a simple description
Link:
NOTE: Please watch the video or ask us through Slack if something is not clear for you. We usually don't change the points after the deadline.