Locality Sensitive Distributed Computing
Lecturer: Prof. David Peleg (Weizmann Institute of Science, Israel).
About the lecturer | Abstract | Slides | Assignment
About the lecturer:
David Peleg, received his BSc degree from the Technion in Haifa in
1980, MSc from Bar-Ilan University in 1982 and PhD from the Weizmann
Institute of Science in Rehovot in 1985.
He is currently a full professor in the Weizmann Institute of Science.
His research interests include graph algorithms, approximation
algorithms, distributed computing and communication networks. He is an
author of more than 200 publications in these areas.
In recognition of his work, he was invited to serve as an editor of
computer science journals (Theoretical Computer Science, Parallel
Processing Letters, Networks) and as a program committee member of
most influential conferences like STOC, FOCS, SODA, PODS (chair),
ICALP and many other.
He advised 8 PhD students.
Course summary: The mini-course will discuss distributed network algorithms based on locality sensitive network representations. It will be composed of three stages:
- brief introduction to distributed network algorithms (looking at some example tasks such as tree construction, broadcast, maximal independent sets, synchronizers and routing),
- presentation of efficient locality-based network representations (such as sparse partitions / covers / decompositions, low-stretch spanners and compact labeling schemes),
- revisiting some basic distributed tasks, this time presenting solutions relying on efficient local representations.
D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM monographs on discrete mathematics and applications SIAM, Philadelphia, PA, 2000.
- Lectures from Nov 29-30 [PPS]
- Exercises from Nov 29 [PPS]
- Lectures from Jan 17-18 [PPS]
- Exercises from Jan 17-18 [PPT]
Assignment: [PDF]
due Sun, March 2.
Please send your solutions in PDF by e-mail to
david DOT peleg AT weizmann DOT ac DOT il.