2/4/2014EE, Meyer TBA

 

Low-Congestion Distributed Algorithms

Boaz Patt-Shamir

Tel Aviv University

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.

8/4/2014CS, Taub 337

 

NetFPGA: The Flexible Open-Source Networking Platform

Noa Zilberman

University of Cambridge

The NetFPGA is an open platform enabling researchers and instructors to build high-speed, hardware-accelerated networking systems. The NetFPGA is the de-facto experimental platform for line-rate implementations of network research and it has a family of boards, supporting from 1GE to 100GE.

The target audience is not restricted to hardware researchers: the NetFPGA provides the ideal platform for research across a wide range of networking topics from architecture to algorithms and from energy-efficient design to routing and forwarding. The most prominent NetFPGA success is OpenFlow, which in turn has reignited the Software Defined Networking movement. NetFPGA enabled OpenFlow by providing a widely available open-source development platform capable of line-rate and was, until its commercial uptake, the reference platform for OpenFlow. NetFPGA enables high-impact network research.

Bio: Noa Zilberman is a Research Associate in the System Research Group, University of Cambridge' Computer Laboratory. Her research interests include open-source network & computing research using the NetFPGA platform, network performance, routing and switching architectures, memories architecture and performance, Internet measurements and topology. In her last roles before joining the System Research Group, she was a researcher in the DIMES project and a chip architect in Broadcom's Network Switching group.