2017/2018 Edition

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:

  1. brief introduction to distributed network algorithms (looking at some example tasks such as tree construction, broadcast, maximal independent sets, synchronizers and routing),
  2. presentation of efficient locality-based network representations (such as sparse partitions / covers / decompositions, low-stretch spanners and compact labeling schemes),
  3. 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.

Lecture slides

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.