Asynch Bellman–Ford

Summary

• Utilized multi-threading and concurrent primitives (threads, mutexes & condition variables in C++11 Thread Support Library) to develop a simple simulator which simulates an asynchronous distributed system composed of one master thread and n slave threads.
• Implemented coordinated behaviors between the master thread and n slave threads by using monitors consisting of mutexes and condition variables
• Implemented message passing in bidirected FIFO links between two slave threads by using mutexes and queues
• Implemented Asynch Bellman–Ford for shortest paths from a single source node i0 to all of the other nodes in a weighted undirected graph under the framework of this simulator.

Project Information

• Course: Distributed Computing (CS 6380)
• Professor: Subbarayan Venkatesan
• Semester: Fall 2016
• Programming Language: C++
• Build Tool: CMake

Full Requirements

Part One: Simulator

• You will develop a simple simulator that simulates an asynchronous distributed system using multithreading.
• There are n + 1 processes in this asynchronous distributed system: one master process and n slave processes. Each process will be simulated by one thread.
• The master thread will "inform" all slave threads as when one round starts.
• You should view duration of one round as one "time unit" ticks in this asynchronous distributed system.
• Each slave threads must wait for the master thread for a "go ahead" signal before it can begin round r.
• The master thread can give the signal to start round r only if it is sure that all the n slave threads have completed their previous round r - 1.
• The message transimission time for each link for each message is to be randomly chosen using a uniform distribution in the range 1 to 15 "time units".
• All links are bidirectional and FIFO. (FIFO: If I send two messages m1 and then m2 to you, then you receive m1 first and then m2.)

Part Two: Bellman–Ford

• You will implement the asynchronous Bellman–Ford algorithm for shortest paths.
• The nodes (processes) and links operate in such a way that message processing time at a node is in one system "time unit" viewed as instantaneous.
• As soon as a message is received, it is processed by that node.
• Your program will read in the network infomation by using adjacency-like matrix from an input file called connectivity.txt:
  1. The first line is n,x: n is number of nodes and they are labeled as 1..n and x (<= n) is the id of the root aka (i0) of the shortest paths tree.
  2. The remaining is adjacency-like matrix denoted as M indicating connectivity infomation.
  3. Specifically, M[i][j] shows the weight of link between node i and j. A weight of -1 signifies no link.
• The master thread reads connectivity.txt and then spawns n threads.
• No process knows the value of n. No slave threads knows who is i0.
• All processes must terminate properly after shortest path is found.