Paola Flocchini

Professor at the University of Ottawa, Canada

Title: Moving and Computing: Changing Shape and Dancing under Sequential Schedulers

Abstract

In theoretical computer science, the study of swarms of autonomous mobile robots has concentrated on computational entities operating in Look-Compute–Move (LCM) cycles in the Euclidean space. The computational issues arising in such settings are viewed as due to the interplay between the robots' capabilities and the adversarial power of a scheduler controlling the timing of their activations and the duration of their operations. The focus of research has been on determining the minimal capabilities that allow the robots to solve a given problem under a particular scheduler. In the standard model, OBLOT, the robots are identical, silent, and oblivious: they have no distinguishing features, cannot explicitly communicate, and retain no memory between cycles; in a variant of this model, LUMI, the robots are endowed with a constant amount of persistent memory and of communication. Both models have been extensively investigated under synchronous schedulers, where time is divided into rounds and in each round a non-empty subset of robots is activated and executes an LCM cycle simultaneously. These investigations have largely ignored so far the class of sequential schedulers, in which only one robot is activated in each round. This talk examines the computational power of the robots operating under sequential schedulers in relation to pattern formation problems, showing that this power is much stronger than the obvious capacity of symmetry breaking, and thus of leader election. For example, under any sequential scheduler, robots are capable of solving problems that remain unsolvable under a fully synchronous scheduler, even when a leader is present.

Christian Scheideler

Professor at the University of Paderbord, Germany

Title: Supervised Distributed Computing

Abstract

I will introduce a new framework for distributed computing that extends and refines the standard master-worker approach of scheduling multi-threaded computations. In this framework, there are different roles: a supervisor, a source, a target, and a collection of workers. Initially, the source stores some instance I of a computational problem, and at the end, the target is supposed to store a correct solution S(I) for that instance. We assume that the computation required for $S(I)$ can be modeled as a directed acyclic graph G=(V,E), where V is a set of tasks and (v,w)  in E if and only if task w needs information from task  v in order to be executed. Given G, the role of the supervisor is to schedule the execution of the tasks in G by assigning them to the workers. If all workers are honest, the workers have access to the source and target, and information can be exchanged directly between the workers, the supervisor only needs to know G to successfully schedule the computations. I.e., the supervisor does not have to handle any data itself like in standard master-worker approaches, which has the tremendous benefit that tasks can be run massively in parallel in large distributed environments without the supervisor becoming a bottleneck. But what if some of the workers are adversarial? Interestingly, I will show that under certain assumptions a data-agnostic scheduling approach would even work in an adversarial setting where the majority of workers is adversarial while keeping the work overhead for the honest workers close to the case that all workers are honest. This is joint work with John Augustine, Henning Hillebrandt, Manish Kumar, and Julian Werthmann.

Stefan Schmid

Professor at the Technical University of Berlin, Germany

Title: Revolutionizing Datacenter Networks with Reconfigurable Topologies: Vision, Algorithmic Foundations and Challenges

Abstract

With the growing popularity of data-intensive applications related to machine learning, datacenter networks have become a critical infrastructure for our digital society. Given the explosive growth of datacenter traffic and the slowdown of Moore’s law, significant efforts have been made to improve datacenter network performance over the last decade. A particularly innovative solution is reconfigurable datacenter networks (RDCNs): datacenter networks whose topologies dynamically change over time, in either a demand-oblivious or a demand-aware manner. Such dynamic topologies are enabled by recent optical switching technologies and stand in stark contrast to state-of-the-art datacenter network topologies, which are fixed and oblivious to the actual traffic demand. In particular, reconfigurable demand-aware and “self-adjusting” datacenter networks are motivated empirically by the significant spatial and temporal structures observed in datacenter communication traffic. In this talk, we present an overview of reconfigurable datacenter networks. In particular, we discuss the motivation for such reconfigurable architectures, review the technological enablers, and present a taxonomy that classifies the design space into two dimensions: static vs. dynamic and demand-oblivious vs. demand-aware. We discuss different architectures and protocols for such networks and point out research challenges for researchers interested in the algorithmic foundations.

Bio

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, an ERC Consolidator Grant 2019, and an ERC Proof-of-Concept Grant 2026.