Krill Prize 2016
Dr. Keren Censor-Hillel
Research Topic: The computational power of distributed computing models
As a constantly increasing number of technologies involve computing on a large scale, manyof them rely on distributed systems. These systems consist of multiple computing components that do not rely on centralized control. Examples of paramount importance
include huge networks or databases used by large companies, as well as social or economic networks. The significance of such systems makes it vital that we understand the fundamental theory that underlies distributed computation. The goal of my research is to unify and compare models of distributed computation. In other words, my high-level goal is to provide exact measures that separate hardness that is attributed to the system
weaknesses from the difficulties that arise from each specific problem.
The main paradigm for distributed systems is considering them as graphs. The computing
components are represented by vertices and the communication links by edges. The
complexity measure of a distributed algorithm that we aim to minimize is the amount of
communication required in order to execute a given task.
A huge amount of research has been devoted to understanding computation in the above
basic setting (the Local model). This model is aimed at abstracting away many uncertainties that arise in distributed computing, such as lack of global clocks, faulty components, or errors in communication. Because this model is clean and captures some of the main challenges that distributed computing faces, significant progress has been made and the complexity of many computations is fairly well-understood.
In my research, I address the fundamental question of what happens to the computation
when practical limitations are brought back into the picture.One example for this is communication restrictions, such as a limit on the size of messages (the Congest model) or on the congestion at each node (the Broadcast-Congest model). My previous results provide algorithms for globally disseminating information in the Congest and Broadcast-Congest models as well as lower bounds for doing so. The methods used include novel distributed connectivity decomposition algorithms and analysis of connectivity after
randomly sampling a graph. I also study the robustness of algorithms in these models against failures, with some new randomized techniques presented by a graduate student of mine and myself.
A second line of study I pursue is the Clique model of computation, in which the
communication graph is complete, and is separated from the graph whose attributes are
required to be studied. This model attempts to separate the hardness of computation that
arises from distances in the communication graph, from that which is caused by congestion over the links. Along with a graduate student of mine and collaborators, I recently obtained an exciting result that gives us ability to use algebraic techniques for distributed computations in this model. Our ultimate goal is to use these techniques for solving problems in the more realistic but harder Congest model, by simulating the Clique in dense parts of the network graph. A third example for practical limitations on distributed computing is the possibility of errors in communication. This can be caused by collisions in a wireless network, or by any other type of noise or fault in the system. An important tool that comes into play is the ability to use coding for the information that is sent. This constitutes another line of research that I pursue, in which I provided coding techniques for additive wireless networks, and I plan to study coding for additional settings that are prone to errors. My work provides an important complement to the combined efforts of the distributed computing community to study and understand particular distributed tasks. Moreover, my work typically has impact on theoretical computer science in general. One example is my work in the Broadcast-Congest model of computation, which led us to obtain bounds on the vertex connectivity of subgraphs induced by sampling, a question of high importance to graph theory.