Mini-Project on Distributed Graph Coloring and Channel Allocation
Class number: 202-1-4071
Schedule: Thursday 10:00-12:00
Bldng 34, Auditorium 114
Office Hours: Tue. 14:00-16:00
Bldng 37, Auditorium 217
The aim of this mini-project is to familiarize students with the research in the area. The students will be required to read a paper or two on this subject, to implement an algorithm described in this paper, and to experiment with this algorithm.
There will be one lecture on
Thur., 10:00-12:00, March 16, in Building 34, Hall 114. On this lecture the
students will be introduced to the area, and will be told about the papers
they can choose. Within three weeks after the beginning of the semester, the
students are supposed to choose a paper, and to inform the teacher of their
choice. The work can be done in pairs.
The focus in this mini-project will be on distributed algorithms for coloring graphs, and other symmetry-breaking problems, including computing Maximal Independent Set and Maximal Matching. Algorithms for these problems are widely used as subroutines for numerous other distributed algorithms. Therefore, improving algorithms for these problems is of large practical importance. Indeed, this research area was very active in recent years. Morever, these problems seem to encapsulate many important aspects of Distributed Computing. Thus, by studying these algorithms the students will get familiarized with a large magnitude of techniques used elsewhere in the area of Distributed Algorithms.
Most of the material needed for this course can be found in a monograph Distributed Graph Coloring: Fundamentals and Recent Developments, authored by L. Barenboim and myself.
Requirements for the Mini-Project Report
The algorithms should be implemented
using a network simulation on a personal computer.
To this end, you can use Simulator for Network Algorithms.