Distributed Algorithms

Introduction

This project implements the distributed wave and election algorithms taught in CSC8103 at Newcastle University. Trees/graphs are randomly generated and the output and results of each algorithm are displayed in console or Matplotlib depending on the algorithm. Logs are also generated by the algorithms to demonstrate what is happening at each of the processes during execution.

Wave algorithms implemented:

• Tree Algorithm (Algorithm 6.3 [1])
• Echo Algorithm (Algorithm 6.5 [1])

Election algorithms implemented:

• Election Algorithm on Trees (Algorithm 7.1 [2])
• Extinction Applied to The Echo Algorithm (Algorithm 7.9 [2])

Installation

Requirements

To run this application, you need:

• Python 3.10+

Recommended IDE

It is recommended to use the PyCharm IDE to run this project as it produces some graphs (for the echo algorithms) which are better viewed in the SciView panel, which allows you to switch between graphs without saving them.

Running this application outside PyCharm will still work, however you may have to save each graph if you wish to view them at the same time.

Libraries

To install the required Python libraries, run the command:

pip install -r requirements.txt

Running the Algorithms

Tree Algorithm

To run the tree algorithm, run the command:

python main.py tree

The following option is available for this command:

• -p <int> - Sets the number of processes (min: 2, max: 64, default: 8)

The output of this algorithm will produce:

• Tree generated in console
• Logs from the execution in console
• Total number of messages sent between processes in console

Notes:

• The node with the smallest ID will be elected as the leader.
• The total number of messages between processes will be: 2 * (P - 1) where P is the total number of processes

Echo Algorithm

To run the echo algorithm, run the command:

python main.py echo

The following options are available for this command:

• -p <int> - Sets the number of processes (min: 2, max: 64, default: 8)
• -e <int> - Sets the number executions of this algorithm (min: 1, max: 10, default: 1)
• --hide-logs - Hides the logs produced by the algorithm, helpful for multiple executions where many logs are produced (optional)

The output of this algorithm will produce:

• Initial graph generated in Matplotlib
• Logs from each execution in console (if not hidden)
• Each tree generated from each execution in console and Matplotlib
• Total number of messages sent between processes in each execution in console

Notes:

• If the algorithm is executed multiple times, the resulting trees will have the same root however children nodes may vary.
• The total number of messages between processes will be: 2 * E where E is the total number of edges between processes.

Election Algorithm on Trees

To run the tree election algorithm, run the command:

python main.py tree_election

The following option is available for this command:

• -p <int> - Sets the number of processes (min: 2, max: 64, default: 8)

The output of this algorithm will produce:

• Tree generated in console
• Logs from the execution in console
• Total number of messages sent between processes in each execution in console

Notes:

• The node with the smallest ID will be elected as the leader.
• The total number of messages between processes will be: 4 * (P - 1) where P is the total number of processes

Extinction Applied to The Echo Algorithm

To run the echo election algorithm, run the command:

python main.py echo_election

The following options are available for this command:

• -p <int> - Sets the number of processes (min: 2, max: 64, default: 8)
• -i <int> - Sets the number of initiators processes (min: 1, max: 64, default: 1)
• -e <int> - Sets the number of executions of this algorithm (min: 1, max: 10, default: 1)
• --hide-logs - Hides the logs produced by the algorithm, helpful for multiple executions where many logs are produced (optional)

The output of this algorithm will produce:

• Initial graph generated in Matplotlib
• Logs from each execution in console (if not hidden)
• Each tree generated from each execution in console and Matplotlib
• Total number of messages sent between processes in each execution in console

Notes:

• The initiator process with the smallest ID will be elected as the leader.
• If the algorithm is executed multiple times, the same leader will be elected however the resulting trees may vary.
• The total number of messages between processes may vary due to nature of the distributed processes and algorithm.

References

[1] G. Tel, “Wave and Traversal Algorithms,” in Introduction to Distributed Algorithms, 2nd ed., Cambridge: Cambridge University Press, 2000, pp. 181–226.

[2] G. Tel, “Election Algorithms,” in Introduction to Distributed Algorithms, 2nd ed., Cambridge: Cambridge University Press, 2000, pp. 227–267.