link

May 11, Wednesday
12:00 – 13:00

Distributed Algorithms for Symmetry Breaking
Computer Science seminar
Lecturer : Johannes Schneider
Lecturer homepage : http://www.disco.ethz.ch/members/johannes.html
Affiliation : Institute for Computer Engineering and Networks Laboratory (TIK), ETH Zurich
Location : 202/37
Host : Prof. Michael Elkin
Symmetry breaking is an important task for distributed systems. Well-known problems involving symmetry breaking are the coloring and maximal independent set problems. They lie at the heart of many scheduling problems such as computing a TDMA schedule in wireless networks or for scheduling transactions in a multi-core system. In this talk, I consider both problems and look at different graph classes. A few randomized and deterministic algorithms will be presented in the message passing model.