The Locality of Distributed Symmetry Breaking

Friday, April 19, 2013 - 1:00pm to 2:30pm
Location: 
32-G631
Speaker: 
Seth Pettie

How do two pathologically polite people decide who should walk through a doorway first? After some number of iterations of "After you", "No, after you", surely one of them will have the courage to just walk through the damn doorway! But who wants to depend on human courage? They would both feel more comfortable if there were some well-defined protocol to break their initial symmetry. Perhaps a simple rule would work: Youth-Before-Beauty or Beauty-Before-Youth... but aren't we all equally beautiful, approximately? Nodes in distributed systems have to walk through doorways, so to speak, and they're real sticklers for following protocol. In this talk I'll present new (and often provably optimal) randomized algorithms for some classical symmetry breaking tasks in distributed networks: computing maximal independent sets, maximal matchings, and vertex coloring. This is joint work with Leonid Barenboim, Michael Elkin, and Johannes Schneider. A extended abstract of these results appeared in FOCS 2012.