Tuesday, February 16, 2016
Speaker: Keren Censor-Hillel
Venue: TU Wien
For many distributed computing problems there exists a characterizing
combinatorial structure. In other words, the existence of an algorithm
for solving the problem on any graph G in time T(G) implies the
existence of the structure in G with some parameter related to T(G),
and vice versa. Such relations go back to classic examples, such as
synchronizers and sparse spanners, and continue to emerge in recent
studies of gossip algorithms and multicast algorithms in different
communication settings. In this talk I will give an overview of both
old and recent results that illustrate these connections. I will show
how finding distributed algorithms as well as proving lower bounds can
be reduced to studying combinatorial graph structures.
No previous knowledge in distributed computing will be assumed.