Keynotes

Title: Computable Functions in Anonymous Networks

Abstract: In this talk, we present several computability results in anonymous network with broadcast communications. First, we recall the characterization, given by Boldi and Vigna, of the computable functions when agents have no information on their outgoing neighborhoods. Then we characterize the class of computable functions in networks with either (a) output port awareness, (b) bidirectional links, or (c) outdegree awareness: In each case, we prove that a function can be computed if and only it is frequency-based, namely, its value only depends on the frequencies of the different input values. This characterization holds for both exact and approximate computability. Our approach relies on the notion of graph fibration, and the key to our positive result is a distributed algorithm that computes the minimum base of the network.
In the second part of the talk, we tackle the setting of dynamic networks and present a quite different approach based on the popular Push-Sum algorithm: When an upper bound on the network size is available, we provide a more tractable algorithm for computing frequency-based functions, which can cope with dynamic network topology changes.

Bernadette Charron-Bost received the M.Sc. degree in mathematics from Paris Diderot University, Paris, in 1980 and a Ph.D. in Computer Science from the Ecole Normale Supérieure, Paris in 1989. She is currently Director of Research at CNRS and located since 2021 at the department of CS at the Ecole Normale Supérieure in Paris. Much of her work is on fundamental aspects of Distributed Computing, in particular on fault tolerance and computational models for the design and the analysis of fault-tolerant distributed systems. More recently, her research interests also include dynamic networks and asymptotic consensus in multi-agent systems, with application to natural systems.

Title: To Catch a (Distributed) Thief

Abstract: Over the last several years we have seen a boom in the development of new Byzantine agreement protocols, in large part driven by the excitement over blockchains and cryptocurrencies. Unfortunately, Byzantine agreement protocols have some inherent limitations: (a) they are very expensive, particularly in terms of bandwidth; (b) correctness tends to depend on strong assumptions, such as unreliable network behavior; (c) and it is impossible to ensure correct operation when more than 1/3 of the processing power in the system is controlled by a single malicious party. These problems are fundamentally intertwined with the problem of Byzantine fault tolerance. What if, instead of preventing bad behavior by a malicious attacker, we guarantee “accountability,” i.e., we can provide irrefutable evidence of the bad behavior and the identity of the perpetrator of those illegal actions? Much in the way we prevent crime in the real world, we can prevent bad behavior in a distributed system: either the protocol succeeds, or alternatively we record sufficient information to catch the criminal and take remedial actions. (Accountability has been increasingly discussed as a desirable property in blockchains like Ethereum, which “slashes” the stake of cheating users.) In this talk, we give an overview of accountability in distributed systems, with a focus on decision problems like consensus. We begin with Polygraph, a (provably) accountable consensus protocol, and then describe the ABC transformation for making every consensus protocol accountable. Finally, we talk about the underlying theory of accountability and the necessary and sufficient conditions for achieving accountability. This talk covers joint work by Pierre Civit, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, and Adi Serendinschi.

Seth Gilbert is a Dean’s Chair Associate Professor at the National University of Singapore. He received his PhD from MIT, and spent several years as a postdoc at EPFL. His work includes research on backoff protocols, dynamic graph algorithms, wireless networks, robust scheduling, and the occasional blockchain. In fact, Seth’s research focuses on algorithmic issues of robustness and scalability, wherever they may arise.

Title: Towards Learning-Powered Networked Systems

Abstract: Recent years have witnessed a surge of interest in applying machine learning to the design of networked systems. I will discuss my own recent efforts in the context of two fundamental networking challenges: routing and congestion control. Specifically, I will present an online-learning framework for Internet congestion control, and also a novel, deep-learning-based approach to optimizing traffic flow between data centers. Time permitting, I will also discuss recent results on how the safe deployment of such learning-augmented systems can be accomplished.

Michael Schapira is professor of Computer Science at Hebrew University. His research focuses on the design and analysis of (Inter)network architectures and protocols and, in particular, on the interface of networking and machine learning. Prior to joining Hebrew U, he was a visiting scientist at Google NYC’s Infrastructure Networking Group and a postdoctoral researcher at UC Berkeley, Yale University, and Princeton University. He is a recipient of the Wolf Foundation’s Krill Prize, faculty awards from Microsoft, Google, and Facebook, IETF/IRTF Applied Networking Research Prizes, and the IEEE Communications Society William R. Bennett Prize.

Title: Self-adjusting networks [slides]

Abstract: The bandwidth and latency requirements of modern datacenter applications have led researchers to propose various datacenter topology designs using static, dynamic demand-oblivious (rotor), and/or dynamic demand-aware switches. However, given the diverse nature of datacenter traffic, there is little consensus about how these designs would fare against each other. In this talk, I will present the vision of self-adjusting networks: networks which are optimized towards, and “match”, the traffic workload they serve. We will discuss information-theoretic metrics to quantify the structure in communication traffic as well as the achievable performance in datacenter networks matching their demands, present network design principles accordingly, and identify open research challenges. I will also show how the notions of self-adjusting networks and demand-aware graphs relate to classic optimization problems in theoretical computer science.

Stefan Schmid is a Professor at the Technical University of Berlin, Germany. MSc and PhD at ETH Zurich, Postdoc at TU Munich and University of Paderborn, Senior Research Scientist at T-Labs in Berlin, Associate Professor at Aalborg University, Denmark, Full Professor at the University of Vienna, Austria, and Sabbathical as a Fellow at the Israel Institute for Advanced Studies (IIAS), Israel. Stefan Schmid received the IEEE Communications Society ITC Early Career Award 2016 and an ERC Consolidator Grant 2019. Stefan Schmid’s research interests revolve around the fundamental and algorithmic problems of networked and distributed systems.