Seminar on Distributed and Parallel Algorithms

Class number

202-2-5081

Schedule

Sunday, 14:00-16:00, Building 28, Auditorium 203

Outline

The aim of this seminar is to familiarize students with the research in the area of Distributed and Parallel Algorithms. The students will be required to read a paper or a book chapter on this subject, and present it in class.

General information

There will be a number of lectures in the beginning of the course. In these lectures the students will be introduced to the area, and will be told about the topics they can choose. Starting with the third or fourth lecture the students will present papers in class. Students are allowed to work in pairs, but both students in the pair will be required to give a part of the presentation. Students will be required to submit a printed hard-copy of their presentation to the teacher after the presentation.

The grade will be "pass" or "fail". Students will be allowed to miss at most 20% of all meetings without justification.

Syllabys

Network decompositions that are useful in distributed and parallel algorithms will be extensively discussed. In particular, sparse covers, partitions, spanners, shallow-light trees, low-average stretch trees, and other objects of this kind will be studied. Also, we will discuss the sublinear-time distributed algorithm of Garey-Kutten-Peleg for the Minimum Spanning Tree problem, and the lower bound for the MST problem due to Peleg and Rubinovich. In parallel algorithmics we will study Batcher's Odd-Even merging network, merging in PRAM models, simulating CRCW PRAM model in EREW PRAM model, and bitonic sorting network.

Remark: The class in Distributed Algorithms is NOT a prerequisite to this class.

Topics

Sparse Covers, Chapter 12 of the book of David Peleg.

Sparse Partitions, Chapter 13 of the book of David Peleg.

Network Decompositions, Regional Matchings, Chapter 14 of the book of David Peleg.

Spanners, Chapter 16 of the book of David Peleg.

Shallow-Light Trees, Chapter 17 of the book of David Peleg.

The article of Alon-Karp-Peleg-West, 1992. See chapter 18 of of the book of David Peleg.

Distance Labeling - Chapter 19 of the book of David Peleg.

Distributed Minimum Spanning Tree, Garey-Kutten-Peleg algorithm, Chapter 24, pages 273-286 of the book of David Peleg.

Batcher's Odd-Even Merging and Sorting Networks, the book of Pranay Chaudhuri, pages 63-67, 84-86.

Merging in CREW model, Chaudhuri, pp. 67-71.

Simulating CRCW in EREW, Chaudhuri, pp. 71-78.

Bitonic Sorting Network, Chaudhuri, pp.86-89.

Sorting in PRAM models, Chaudhuri, pp. 89-92.

Books

David Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000.

Pranay Chaudhuri, Parallel Algorithms, Prentice Hall, 1989.

Joseph JaJa, An Introduction to Parallel Algorithms, Addison-Wesley Publishing Company, 1992.