Seminar on Distributed and Parallel Algorithms
ScheduleSunday, 14:00-16:00, Building 28, Auditorium 203
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.
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.
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.
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.
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.