This is a student project made for "Distributed Systems" course of department of Informatics - Ionian University. The main purpose of the project is to implement Chang-Roberts Election Algorithm, run it on various networks with ring topology and compare algorithm's complexity-theory (message passes) with the results of the simulations.
Chang-Roberts algorithm is an improved version of LeLann's algorithm for finding the largest (or smallest) of a set of uniquely numbered processes arranged in a circle/ring. This process is also known as "leader election" in which a node is defined as leader and runs a specific task (e.g. makes a decision). Algorithm's functionality is based on the fact that each node, who wants to become leader, sends his ID and if he receives it back then he becomes leader. In case that a node, who wants to win the election, receives an ID larger than his ID, he discards it. Else, if the received ID is smaller, he forwards it to the next node, just like a node, who doesn't want to become leader, does.
This algorithm does n(n + 1)/2 in worst case, 2n – 1 in best case and n log n in average case, total forwards of the messages until the end - election of the leader. (n = number of nodes in network)
- Download and install OMNet++ (tested on 5.6.2 version)
- Run
git clone (git url of the repository)into a directory in order to download the project. - Open OMNeT++ IDE
- Go to
File > Open Project from File System...and define the project directory as the "Import source" - Open the "omnetpp.ini" file and run the simulation.