HW#3 --- last modified April 04 2022 22:58:39.

Solution set.

Due date: Apr 4

Files to be submitted:
  Hw3.zip

Purpose: To gain experience with parallel and distributed algorithms

Related Course Outcomes:

CLO2 -- Analyze or code a parallel algorithm using a thread library

CLO4 -- Analyze the correctness and run time of a distributed algorithm

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw3.zip file. The written part should be in a file Hw3.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it. One problem on the written part and the coding part are related to the vertex coloring problem, that is the assignment of colors (usually represented as numbers 0, 1, 2, ..., k-1) to vertices in a graph, so that if two vertices share an edge then they don't get the same color. Besides being cool for coloring maps, this problem comes up in job scheduling. For example, one could have a list of tasks (vertices) for a business. Two tasks share an edge if they rely on the same hardware or service in such a way that they cannot both be done at the same time. In this setting, colors can be viewed as time slots for executing tasks, so that conflicting tasks don't execute at the same time.

1. Distributed algorithms for vertex coloring often use the multi-trials approach. This is closely related to the choice coordination problem discussed in class. I want you to read the paper: Schneider, J. (2010), "A new technique for distributed symmetry breaking", Proceedings of the Symposium on Principles of Distributed Computing. Write a page summary of the paper. This summary should say how the multi-trials approach is related to CCP. Pick any algorithm in the paper, walk through how it works with a toy example.
2. Give a concrete example with 24 processors where a faulty processor succeeds in foiling a threshold choice in the Byzantine agreement algorithm.

For the coding part of the assignment, I want you to code a parallel algorithm to find vertex colorings (not necessary minimal). One way to produce a valid coloring of the vertices of a graph is to first find a maximal independent set, color these vertices with color 0. Then remove these vertices from the graphs as well as the edges connected to them, making a new graph `G^(1)`. Find a maximal independent set in this graph, color its vertices 1, delete these vertices and associated edges to make a graph `G^(2)`, and repeat the process. At some point, the graph `G^(k)` will be empty, at which point we're done. I want you to implement this idea using threads and the parallel MIS algorithm from class to compute maximal independent sets. Your program will be compiled from the command line using the syntax:

javac VertexColorThreads.java

It will then be run from the command line with a command of the format:

java VertexColorThreads filename_of_file_containing_a_graph

For example,

java VertexColorThreads graph.txt

Here the format of the file filename_of_file_containing_a_graph is a sequence of lines each line consisting of a pair of comma separated nonnegative integers. For example:

1,2
1,4
2,3
4,5
3,5
5,6

Each such line represents one edge in an undirected graph. The particular graph in the example above is the graph used in class when first taking about the maximal independent set problem. The distinct numbers that appear in some edges represent the vertices of this graph. On such an input, your program should output a sequence of lines consisting of pairs vertex_number,color. For example:

1,0
5,0
3,1
4,1
6,1
2,2

The colorings your program will produce won't necessarily be using the minimal number of colors. I would like you to conduct experiments on the number of colors needed for randomly generated graphs of varying numbers of vertices and varying edge probabilities. To generate such graphs I want you to write a program RandomGraph.java. It will be compile with a line like:

javac RandomGraph.java

and run using a line like:

java RandomGraph number_of_vertices some_edge_probability

For example:

java RandomGraph 5 0.5

The output of this program will be a graph in the format usable by your VertexColorThreads.java program. On such an input, RandomGraph cycles through each distinct possible edge of a graph with vertices: 0,1,2,..., number_of_vertices -1, flips a computer implemented coin with bias some_edge_probability, and outputs the edge if the value is the computer equivalent of heads. Put the write-up of the experiments you conducts in Experiments.pdf.

Point Breakdown