Solved-Homework 3 -Solution

Description

1. Modify the Box Sort algorithm to make CREW PRAM algorithm that selects the median of n input numbers in O(logn) steps

using nlogn processors. Assume that the n input numbers are initially located in global memory locations 1 through n.

2. Give a concrete example with 8 processors where the faulty processor succeeds in foiling a threshold choice in the Byzantine agreement algorithm.

3. Carefully give a DMRC algorithm for determine which node in a communications network has the most incoming traffic. Assume the input consist of (key; value) pairs of the form ((i,j);ni,j) where the key is the pair (i,j) and ni,j is the number of bytes of traffic from node i to j in the network.

Modification to Parallel MIS to find Maximum Cliques

1. Construct the dual graph G¹ for given graph G

2. Run Parallel MIS algorithm on graph G¹

3. Return the output of MIS for graph G¹ algorithm as maximum clique for graph G