Algorithms for distributed systems are frequently devised and analyzed in either the LOCAL or the CONGEST model. In both settings, the distributed system is modelled as a graph, where nodes perform arbitrary computations in synchronous rounds and, in each round, exchange messages along the edges. In the LOCAL model, messages may be of arbitrary size, meaning that an r-round algorithm can be interpreted as a function mapping the topology and inputs of a node’s r-neighborhood to the node’s share of the algorithm’s output. In the CONGEST model, message size is restricted, typically to a polylogarithmic number of bits in terms of the input size, restricting algorithms further. Usually, the problem specification is fused to the topology of the communication graph, e.g., one might want to find a maximal independent set or matching of the graph.

In this talk, I will discuss a different setup: in each round, each node can send a (different) message of logarithmic size to each other node. This enables to obtain information from distant parts of an input graph quickly, and there is no communication “bottleneck” imposing potentially unreasonable restrictions on communication. This removes the main obstacles of the LOCAL and CONGEST model that give rise to lower bounds, yet in many cases it is non-trivial to devise very fast algorithms. I will motivate the study of this model, illustrate it by some examples, summarize the state of the art, and present a number of open problems in the area.

In this talk I will describe recent advances in communication complexity, which have led for the first time to strong lower bounds on multi-party computation with private channels. These new bounds and techniques hold out the hope of proving lower bounds on distributed graph problems that were previously not approachable, as well as analyzing models for which no good lower bounds currently exist, such as the congested clique model.

I will show a recent lower bound on multi-party set disjointness (to appear in FOCS’13), which was proven using information theory. To prove the lower bound, we prove a direct sum theorem, which shows that the cost of the problem is at least the sum of the costs of many sub-problems; namely, we are able to formally prove that if one wants to check if k sets intersect, then one has to essentially go over each coordinate and check whether that coordinate is in the intersection. The same principle seems likely to apply to distributed testing of graph properties. The set disjointness lower bound yields some distributed lower bounds, and I will conclude by discussing open problems and exciting directions to extend these results.

Suppose that every vertex of an n-vertex graph G = (V, E) of maximum degree Δ hosts a processor. These processors wake up simultaneously and communicate in discrete rounds. In each round each vertex is allowed to send an arbitrarily large message to all its neighbors. We are interested in coloring this graph with a relatively few colors within a small number of rounds. At the end of the algorithm each vertex needs to know its own color. This problem is closely related to problems of computing a maximal independent set and a maximal matching in the distributed setting.

In this talk I plan to overview the rich history of the research on these problems, to mention the most important known results, and describe some of the basic techniques which are used to achieve them. Then I will turn to my own recent work on both deterministic (joint with Barenboim, JACM’11) and randomized (joint with Barenboim, Pettie and Schneider, FOCS’12) variants of these problems. Specifically, I will show an outline of the deterministic Δ^1+ε-coloring algorithm that requires polylogarithmic in n number of rounds. (Here ε > 0 is an arbitrarily small constant.) This result solves an open problem posed by Linial in 1987. If time permits I will also show an outline of a randomized (Δ + 1)-coloring algorithm that requires O(log Δ) + exp(O((log log n)^1/2)) number of rounds.

There is a huge number of open problems in this area. During the talk I will present and discuss some of them.

Load Balancing is a crucial ingredient for the efficient utilization of shared resources. As we are at the end of an era of increasing individual processor power, more and more computations are performed on decentralized networks.

In one of the standard models of load balancing, processors are represented by nodes of a graph, while links are represented by edges. The objective is to balance the load by allowing vertices to exchange loads with their direct neighbors. In this talk we are interested in minimizing the discrepancy of the load, that is, the difference between the maximum loaded and minimum loaded processor.

In the first part we discuss several aspects of our model, including the relation between Markov chains and iterative load balancing algorithms under the assumption that load is arbitrarily divisible. The second (and main) part of this talk covers a more realistic setting with unsplittable jobs and analyzes a natural randomized rounding-based strategy. We analyze this strategy for hypercubes first and then turn to the general setting of arbitrary graphs.

We argue that grid structures are a very promising alternative to the standard approach for distributing a clock signal throughout VLSI circuits and other hardware devices. Traditionally, this is accomplished by a delay-balanced clock tree, which distributes the signal supplied by a single clock source via carefully engineered and buffered signal paths.

Our approach, termed HEX, is based on a hexagonal grid with simple intermediate nodes, which both control the forwarding of clock ticks in the grid and supply them to nearby functional units. HEX is Byzantine fault-tolerant, in a way that scales with the grid size, self-stabilizing, and seamlessly integrates with multiple synchronized clock sources, as used in multi-synchronous Globally Synchronous Locally Asynchronous (GALS) architectures. Moreover, HEX guarantees a small clock skew between neighbors even for wire delays that are only moderately balanced. We provide both a theoretical analysis of the worst-case skew and simulation results that demonstrate very small typical skew in realistic runs.

(Coauthored by Danny Dolev, Matthias Függer, Christoph Lenzen, Martin Perner, and Ulrich Schmid.)