Arvutiteaduse instituut
  1. Kursused
  2. 2022/23 kevad
  3. Hajussüsteemid (LTAT.06.007)
EN
Logi sisse

Hajussüsteemid 2022/23 kevad

  • General
  • Lectures
  • Practical work
  • Study materials
  • Plagiarism
  • Practical work submission
  • Message board

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

Leader Election

Bully Vs Ring Algorithm

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Courses’i keskkonna kasutustingimused