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.
Give a concrete example with 8 processors where the faulty processor succeeds in foiling a threshold choice in the Byzantine agreement algorithm.
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
Construct the dual graph G1 for given graph G
Run Parallel MIS algorithm on graph G1
Return the output of MIS for graph G1 algorithm as maximum clique for graph G
