vecentpotter / distributed-graph-algorithms

Distributed Graph algorithms in DistAlgo

Distributed Graph Algorithms in DistAlgo

This repository contains the implementations of some distributed graph algorithms as well as two token-based mutex algorithms in DistAlgo. DistAlgo is a superset of Python that adds special constructs to Python for specifying distributed algorithms in a high-level and succint manner. DistAlgo programs get compiled to portable Python 3 code. DistAlgo was developed at the Department of Computer Science in Stony Brook University. It is used in the instruction of some graduate courses such as CSE 535 Asynchronous Systems by Annie Liu and CSE 594 Distributed Systems by Scott Stoller.

The Distributed Graph Algorithms

The following distributed graph algorithms that have implemented using DistAlgo-0.2:

1. Minimum Spanning Tree
2. Maximal Independent Set
3. Breadth First Search
4. Shortest Path

The subdirectory of each algorithm contains a relevant ReadMe file that describes the algorithm in detail with specific information about its implementation, limitations, etc. The ReadMe should be viewed in GitHub or with a Markdown converter as it contains images, styling, sections, etc.

Note about References

All references have been hyperlinked in-place using Markdown's link syntax.

NetworkX

A graph library known as NetworkX was used in this project. It is a well-renown pure Python library that provides several useful features pertaining to graphs. Granted, it was a bit unnecessary for this project, but I was anticipating more use for it than was needed.

Code Length

This is measure and sum of the lines of code of files containing code that were written over the course of this project:

File name	sloc only	all lines
MST.dis.py	319	421
MIS.dis.py	158	212
BFS.dis.py	119	154
ShortestPath.dis.py	43	60
graph_gen.py	75	101
InputGraph.dis.py	36	50
tools.py	67	95
TOTAL (proper)	817	1093
Kruskal.py	69	93
mst_attempt_1.dis	204	276
mst_attempt_1.dis	186	247
TOTAL (incl other)	1276	1709

Notes on the line count

• Other files such as run.py and sequential_messaging_test.dis, that were not directly relevant to project have not been listed above.
• TOTAL (proper) is the line count for all the active project code. Kruskal.py and mst_attempt_* were experimental files written while developing MST and are no longer used.
• Two slightly different versions of InputGraph.py is used by BFS and Shortest Path to process the graph; the count is for the longer one.
• tools.py is used by MST for non-core functionalities (like building the graph, visualizing, etc.)

Frivolous Musings

Lines of Code have never really been a good statistic on how long it took to write a piece of code. In addition, certain languages are more dense than others. For example this segment of Python code extracts lines from a graph file under certain constraints: ... for ed in (e.strip() for e in f.readlines() if e.strip() != "") if len(ed.split()) == 3. It probably would however have taken several lines of code if written in Java. Also, Andrew Tanenbaum mentions in one his awesome books (quoting Fred Brooke's mythical man-moth I believe) how IBM measured the performance of their programmers based on how many lines of code they wrote -- in assembly. Needless to say, the project (OS/360) wasn't very successful.

Other

Ricart-Agrawala's and Suzuki-Kasami's token-based distributed mutex algorithms have also been been implemented in DistAlgo-0.2. In addition, Lamport's fast mutual exclusion and bakery algorithms have been implemented using the built-in Python library threading.