Distributed Algorithms as Combinatorial Structures

VCLA will host a talk by Keren Censor-Hillel on Tuesday, February 16, 2016.

ABSTRACT

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.