The tutorial provides an overview of the principles and "pearls'' of constructing, maintaining and optimizing network topologies, such as peer-to-peer overlays or datacenter interconnects. The tutorial consists of two parts:

• Self-stabilization: In the ...

Restricting the bandwidth in models of distributed graph computations naturally introduces challenges that arise due to communication bottlenecks. In this talk, I will survey techniques for proving lower bounds on the complexity of fundamental graph ...

The notion of summarization is to provide a compact representation of data which approximately captures its essential characteristics. If such summaries can be created, they can lead to efficient distributed algorithms which exchange summaries in order ...

We briefly describe an efficient lock-free concurrent stack design with tunable and tenable relaxed semantics to allow for better performance. The design is tunable and allow for a continuous monotonic trade of weaker semantics for better throughput ...

We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a ...

We investigate stochastic, distributed algorithms that can accomplish separation and integration behaviors in self-organizing particle systems, an abstraction of programmable matter. These particle systems are composed of individual computational units ...

This paper gives a brief presentation of a comprehensive study on the necessary and sufficient state space conditions for the deterministic naming task in the population protocol model. This problem is studied under various combinations of model ...

We investigate the minimum record needed to replay executions of processes that share causally consistent memory. For a version of causal consistency, we identify optimal records under both offline and online recording setting. Under the offline setting, ...

A population protocol describes a set of state change rules for a population of n indistinguishable finite-state agents (automata), undergoing random pairwise interactions. Within this very basic framework, it is possible to resolve a number of ...

We give deterministic distributed (1+ε)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( 1/ε logn) rounds, and our independent set algorithm has a ...

A standard design pattern found in many concurrent data structures, such as hash tables or ordered containers, is an alternation of parallelizable sections that incur no data conflicts and critical sections that must run sequentially and are protected ...

Geo-distributed services that are executed across multiple sites at a global scale are increasingly prevalent, and are at the core of the control plane tasked with managing the Virtual Network Functions (VNFs) of next-generation network infrastructure. ...

We consider the exploration problem in undirected graphs without node labels, which requires that a mobile agent initially placed at an arbitrary node visits all nodes and terminates. We assume that both of the agent and nodes are equipped with little ...

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the deterministic leader election problem with an asymptotically optimal round complexity. Using this result, we ...

Distributed network optimization problems, such as minimum spanning tree, minimum cut, and shortest path, are an active research area in distributed computing. This paper presents a fast distributed algorithm for such problems in the CONGEST model, on ...

Energy is often the most constrained resource in networks of batterypowered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy ...

We present a deterministic distributed algorithm to compute all-pairs shortest paths (APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in Õ (n^3/2 ) rounds in the Congest model, where n is the number of nodes in the graph. This ...

In the uniformity testing problem, we are given access to samples from some unknown distribution μ on a fixed domain \set1,..,n , and our goal is to distinguish the case where μ is the uniform distribution from the case where μ is ε-far from uniform in ...

Interactive proof systems allow a resource-bounded verifier to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee that the prover can only convince the verifier of ...

This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles.

Gossip algorithms, which allow each node to contact a uniformly random other node in each round, have been intensely studied and been adopted in many ...