MiniProject on
Distributed Graph Coloring and Channel Allocation
Class number:
20214071
Schedule: Sunday
14:0016:00
Bldng 34, Auditorium 205 Office Hours:
Tue. 14:0016:00
Bldng 37, Auditorium 217 Outline
The aim of this miniproject 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. General
information
There will be one lecture on
Sun., 14:0016:00, Nov. 22, in Building 34, Hall 205. 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. Syllabys
The focus in this miniproject will be on distributed algorithms for coloring graphs, and other symmetrybreaking 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. Literature
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. Projects
Requirements for
the MiniProject Report

The algorithms should be implemented
using a network simulation on a personal
computer.
To this end, you can use Sinalgo Simulator for Network
Algorithms.