HW#3 --- last modified March 26 2019 00:03:48.

Solution set.

Due date: Apr 8

Files to be submitted:
  Hw3.zip

Purpose: To gain experience with distributed algorithms

Related Course Outcomes:

The main course outcomes covered by this assignment are:

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

CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL

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.

1. Devise a CREW PRAM algorithm that generates a random permutation in `O(log n)` steps. Give a `Theta`-bound on the number of bits randomness it uses and number of processors needed by your algorithm.
2. Give a concrete example with 16 processors where a faulty processor succeeds in foiling a threshold choice in the Byzantine agreement algorithm.
3. Carefully give a DMRC algorithm for determining in a communications network the median incoming network traffic to a node. Assume the input consist of (key; value) pairs of the form `((i,j);n_{i,j})` where the key is the pair `(i,j)` and `n_{i,j}` is the number of bytes of traffic from node `i` to `j` in the network.

A triangle independent set is a set of vertices in a graph none of which share a triangle. Let MTIS (maximal triangle independent set) be the problem of finding a largest set of vertices in a graph none of which share a triangle. Modify our ParallelMIS algorithm so that it instead computes maximal triangle independent sets. Redo the arguments from class as part of your HW3 write-up to show your algorithm has similar properties as the ParallelMIS algorithm. For the coding part of the assignment I would like to code your Parallel MTIS algorithm using Java threads. Your program will be tested from the command line as follows:

javac ParallelMTIS.java
java ParallelMTIS graph_file

0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 0 1 0
1 0 0 0 1 0
0 0 1 1 0 1
0 0 0 0 1 0

On such an input your program should output a maximal triangle independent set. For example, on the above input it outputs:

0
1
2
3
4
5

In this case here, the original graph did not have triangles, so all vertices are output. Each vertex in the independent set is listed on its own line from least to greatest. Again, I substracted 1 off each vertex names I used on the slide. In general, not all vertices in the original graph would be output. For example, consider the case of two triangle with vertices 0,1,2 and 2,3,4 respectively. I.e., they share vertex 2. Then possible maximal triangle sets are: 0,3 or 0,4 or 1,3 or 1,4 or 2.

Point Breakdown