CS342: Algorithms for Parallel and Distributed Systems CS342: Active Exercise 5, Part a Groups: 1. Boris Mizhen, Boris Z., Chuck Russo, B. Knapp 2.Roslin Deputron, Shafik Yaghmour, Eduard Nudelman, Igor S. 3. Yonah Wolf, Oleg Iakounenko, Vitaly D., Alex In this exercise we will explore a number of algorithmic issues that arise in parallel and distributed databases. The elements of the assignment will be distributed in several phases over the next few weeks; the final project is due December 11th, 9AM. This is a firm deadline. The final project will be due the Monday after Thanksgiving. A progress report is due on November 20th. The progress report will count for 25 percent of your final grade and should contain an initial implementation and timings of the sorting algorithm and proposed solutions for the other problems. It should also discuss who is responsible for which part of the project. Note that there will be one additional small project in the course as well; it will be geared towards taking 4-8 hours of programming. This will also be due on the 11th. Therefore you should get a head start on things. The topics we will cover are as follows. 1. Sorting 2. Parallelizing the Relational Join 3. Consistency of Distributed Files 4. File Allocation in Distributed Systems This handout discusses sorting. Sorting is critical in a number of basic applications, I is interesting to study theoretically, and offers a wealth of novel parallel solutions. The richness of the problems arises in part because it fundamentally requires both communication as well as computation. Thus sorting is an excellent area in which to investigate the translation from theory to practice of novel parallel algorithms.'' (Culler et. al, 1992) In this first part you will evaluate several sorting algorithms, decide which is most appropriate for our network of workstations, and implement that algorithm. Again, a pizza and free books will go to the best sorting algorithm. There are two goals in this effort. One is to implement a fast sort, that will sort on the order of one million 32-bit integer keys per each processor reasonably quickly. The second will be to understand several different parallel sorting algorithms; these algorithms will be fair game for the final. I am distributing three papers: 1. Tight Bounds on the Complexity of Parallel Sorting, by Tom Leighton. This paper discusses Columnsort. . A Comparison of Sorting Algorithms for the Connection Machine CM-2 by Blelloch et. al. 3. A few more pages from the ``logP paper'' by Culler et. al. This may provide ideas on implementing Odd-Even Merge Sort. You are to use the next week in class (and out of class) to work through these papers and decide on an appropriate algorithm. On Monday the 11th I'll meet with each group to discuss your choices and assess your understanding of the algorithms. I'll also make data (to sort) available by the 11th.