CS553 Distributed Algorithms Project

Overview

This repository showcases the implementation of a variety of distributed algorithms, such as Snapshot, Wave, Deadlock Detection and Election Algorithms. It executes a menu driven program for eight distributed algorithms on graphs created by NetGameSim and some special topologies like ring.

Design Rationale

The project has been modularized for code reusability and better readability. The project directory tree looks like this:

Project Structure

├── README.md
├── build.sbt
├── project
│   └── build.properties
└── src
    ├── main
    │   ├── resources
    │   │   ├── NetGraph_21-04-24-18-24-58.ngs.perturbed.dot
    │   │   ├── NetGraph_30-03-24-18-54-55.ngs.dot
    │   │   ├── application.conf
    │   │   ├── graph_50_nodes.dot
    │   │   ├── inputEcho.dot
    │   │   └── inputTarry.dot
    │   └── scala
    │       └── main
    │           ├── Main.scala
    │           ├── algorithms
    │           │   ├── BrachaTouegAlgorithm.scala
    │           │   ├── ChandyLamportAlgorithm.scala
    │           │   ├── ChangRobertsAlgorithm.scala
    │           │   ├── EchoAlgorithm.scala
    │           │   ├── FranklinAlgorithm.scala
    │           │   ├── LaiYangAlgorithm.scala
    │           │   ├── TarrysAlgorithm.scala
    │           │   └── TreeAlgorithm.scala
    │           ├── processes
    │           │   ├── BrachaTouegProcess.scala
    │           │   ├── ChandyLamportProcess.scala
    │           │   ├── ChangRobertsProcess.scala
    │           │   ├── EchoProcess.scala
    │           │   ├── FranklinProcess.scala
    │           │   ├── LaiYangProcess.scala
    │           │   ├── TarryProcess.scala
    │           │   └── TreeProcess.scala
    │           └── utility
    │               ├── ApplicationProperties.scala
    │               ├── FranklinOrchestrator.scala
    │               ├── MessageTypes.scala
    │               ├── ProcessRecord.scala
    │               ├── SnapshotUtils.scala
    │               ├── Terminator.scala
    │               └── TopologyReader.scala
    └── test
        └── scala
            ├── ChangRobertsTest.scala
            ├── EchoTest.scala
            ├── TarryTest.scala
            ├── TreeTest.scala
            ├── brachaTouegTest.scala
            ├── chandyLamportTest.scala
            ├── franklinTest.scala
            └── laiYangTest.scala

Project Component Description

• Main.scala - This is the entry point of the project.

• algorithms package - Package containing all the specific algorithm trigger files. These files prepare test data, create Actor classes and trigger the initiators for the algorithms.

• processes package - Package containing all the Actor logic required for algorithms. Algorithm package classes create instances of these Actor classes for running the algorithm.

• utility package - Package containing utility and reusable code common for all algorithms.

  • ApplicationProperties : This is a utility file to read properties from application.conf.
  • MessageTypes : This file has all the message types used by Actors.
  • Terminator : A utility Actor class to help terminate Actor system when an algorithm has ended.
  • TopologyReader : A utility class to read network topology from test data files.
  • FranklinOrchestrator: A utility class to manage rounds for Franklin's Algorithm.
  • SnapshotUtils: A Utility class to store and log data for Snapshot Algorithms.

• resources package - Package containing static files containing Application.conf, and graph test data for creating network for running algorithms

• application.conf - This file has references to the static variables containing the network topolgy used in the algorithms.

• src/test - Package containing test unit tests for all algorithms.

How to run project

From Intellij IDE

Requirements:

1. Java 8 or higher
2. Scala Plugin installed

Steps to Follow :

• Step 1. Clone this repo to your local machine.

   git clone https://github.com/TomarGunjan/CS553-DistributedAlgorithms.git
  

• Step 2. Open the project in IntelliJ

• Step 3. Navigate to src/main/scala/main/Main.scala

• Step 4. Run Main.scala file

Note

Navigate to src/test/scala and run the unit tests for each algorithm from the test files.

From Terminal

Requirements:

1. Should have scala installed

Steps to Follow :

• Step 1. Clone this repo to your local machine.

   git clone https://github.com/TomarGunjan/CS553-DistributedAlgorithms.git
  

• Step 2. Navigate into the Project folder

• Step 3. Run following command

   sbt clean compile run
  

Note

Run following command to execute the entire testing suite.

sbt test

Test Data

Data Type - From NetGameSim

Example of a perturbed graph generated by NetGameSim and visualzation of the same. This is being used for the Tree and Snapshot Algorithm.

Data Type - Manually Created Topology

The ApplicationProperties file read configurations from application.conf file. The Algorithm code then creates network for running algorithm using this data.

Output

This a menu driven program. On running the program the user is presented with a menu to to run any algorithm by selecting an option between 1-8 or 9 to exit the application as shown below.

Below is a sample output from the Bracha Toueg Algorithm. Logs from SLF4J are used to describe progress of algorithm which can be followed on the terminal.

References

1. NetGameSim by Prof. Mark Grechanik
2. Distributed Algorithms, Second Edition - An Intuitive Approach By Wan Fokkink
3. Akka Documentation

Appendix - Algorithm Descriptions

1. Snapshot Algorithms

The Snapshot Algorithm, refers to the process of capturing a consistent global state of the system at a specific point in time. It allows processes to record their local states and messages exchanged, facilitating the observation of the distributed system's behavior for debugging and analysis purposes.

• Chandy-Lamport Algorithm: A snapshot algorithm that is used in distributed systems for recording a consistent global state of an asynchronous system.
• Lai-Yang Algorithm: A snapshot algorithm used for taking consistent global snapshots of a distributed system. This algorithm does not enforce the FIFO property of channels.

2. Wave Algorithm

A wave algorithm is a type of distributed algorithm used for propagating information within a distributed network of nodes.

• Tarry Algorithm: Coordinates process traversal in a distributed system, ensuring a predetermined order of visitation and enabling synchronization.
• Tree Algorithm: Structures the communication network in a hierarchical tree-like fashion, facilitating efficient message propagation and information dissemination.
• Echo Algorithm: A fundamental communication protocol where a message is sent through the network and echoed back by each recipient, confirming its receipt.

3. Deadlock Detection

Deadlock detection is a fundamental problem in distributed computing, which requires determining a cyclic dependency within a running system.

• Bracha-Toueg Algorithm: Employed for deadlock detection in distributed systems. It monitors resource allocation and process interactions to detect potential deadlocks and take corrective actions to resolve them. By proactively identifying and mitigating deadlocks, this algorithm enhances the reliability and availability of distributed systems.

Additonal Implementations

4. Election Algorithm

In an election algorithm, the processes in the network elect one process among them as their leader. The aim is usually to let the leader act as the organizer of some distributed task.

• Chang Roberts Algorithm: Election algorithm for a directed ring which assumes that each process has a Unique Identification (UID). The idea is that only the message with the highest ID will complete the round trip, because every other message is stopped.
• Franklin's Algorithm: Requires an undirected ring, improves on the worst-case message complexity of the Chang-Roberts algorithm. In an election round, each active process compares its own ID with the IDs of its nearest active neighbors on both sides.