The Taub Faculty of Computer Science Events and Talks

The traditional model for computing over a communication network (called LOCAL) allows sending a message of arbitrary size in a single time step. This way, the time complexity is a measure of the locality of algorithms: saying that an algorithm runs in time T is equivalent, under the LOCAL model, to saying that the problem can be solved if each node learns all information the nodes which are reachable within T hops. Therefore, in this model any problem can be solved in time linear in the network diameter.

While work on the LOCAL model has produced many interesting results, it is widely accepted that this model does not capture the true complexity of distributed computing: it is mainly useful in understanding what cannot be done distributively, i.e., lower bounds. A better approximation of reality is the CONGEST model, where a link can carry only a bounded number of bits in a time step. Usually, it is assumed that message size is O(log n) bits, so that each message can carry a constant number of reasonably-sized pieces of information, such as node identifiers, or values of polynomial magnitude. It turns out that in this model, many problems cannot be solved in o(sqrt(n)) time, even in networks of diameter, say, O(log n) hops. On the other hand, letting D denote the network diameter in hops, there are some problems in which the O(D+sqrt(n)) time upper bound is nearly achievable in the CONGEST model (to within a polylogarithmic factor).

In this talk we review some known results in the CONGEST model, as well as some new progress directions. In particular, we will consider the tasks of constructing routing tables, the task of finding a Steiner forest, and the extreme case of a completely connected network (a clique). Bio:
Boaz Patt-Shamir is a Professor of Computer Science in the School of Electrcal Engineering in Tel Aviv University since 1997, where he directs the laboratory for distributed algorithms. Prior to that, he was a professor in Northeastern University in Boston. He received his BSc in Mathematics and Computer Science from Tel Aviv University, his MSc from Weizmann Institute, and his PhD from MIT.

His main research interest is network algorithms, including self-stabilization, clock synchronization, routing, scheduling, and recommender systems. While on sabbatical in HP labs in Cambridge (Ma.), he helped to develop an experimental corporate-intranet search engine based on his ideas for recommender systems.

He has served as the program committee chair for ACM PODC 2008 and SIROCCO 2010, and gave numerous invited talks in scientific conferences.