Sean Chiang, Eileen (Yifan) Zhang, Joshua Yi

1. (4 points) Implement the verifyMIS function. The function accepts a Graph[Int, Int] object as its input. Each vertex of the graph is labeled with 1 or -1, indicating whether or not a vertex is in the MIS. verifyMIS should return true if the labeled vertices form an MIS and false otherwise. To execute the function, run the following:

// Linux
spark-submit --class project_3.main --master local[*] target/scala-2.12/project_3_2.12-1.0.jar verify [path_to_graph] [path_to_MIS]

// Unix
spark-submit --class "project_3.main" --master "local[*]" target/scala-2.12/project_3_2.12-1.0.jar verify [path_to_graph] [path_to_MIS]

Apply verifyMIS locally with the parameter combinations listed in the table below and fill in all blanks.

2. (3 points) Implement the LubyMIS function. The function accepts a Graph[Int, Int] object as its input. You can ignore the two integers associated with the vertex RDD and the edge RDD as they are dummy fields. LubyMIS should return a Graph[Int, Int] object such that the integer in a vertex's data field denotes whether or not the vertex is in the MIS, with 1 signifying membership and -1 signifying non-membership. The output will be written as a CSV file to the output path you provide. To execute the function, run the following:

// Linux
spark-submit --class project_3.main --master local[*] target/scala-2.12/project_3_2.12-1.0.jar compute [path_to_input_graph] [path_for_output_graph]

// Unix
spark-submit --class "project_3.main" --master "local[*]" target/scala-2.12/project_3_2.12-1.0.jar compute [path_to_input_graph] [path_for_output_graph]

Apply LubyMIS locally on the graph files listed below and report the number of iterations and running time that the MIS algorithm consumes for each file. You may need to include additional print statements in LubyMIS in order to acquire this information. Finally, verify your outputs with verifyMIS.

3. (3 points)
   a. Run LubyMIS on twitter_original_edges.csv in GCP with 3x4 cores. Report the number of iterations, running time, and remaining active vertices (i.e. vertices whose status has yet to be determined) at the end of each iteration. You may need to include additional print statements in LubyMIS in order to acquire this information. Finally, verify your outputs with verifyMIS.

b. Run LubyMIS on twitter_original_edges.csv with 4x2 cores and then 2x2 cores. Compare the running times between the 3 jobs with varying core specifications that you submitted in 3a and 3b.

• It seems that while more workers indeed helps reduce running times, the number of cores plays a much greater role in reducing running time.