🪄 Workshop on Analysis of Network Dynamics 🪄

About

WAND is a workshop focusing on the analysis of network dynamics, namely the study of dynamics both on and of networks.

Network dynamics refer to a set of simple protocols that are lightweight and built upon local and elementary rules. Since distributed computing is concerned with how groups of computational agents can efficiently achieve global goals, studying these dynamics is crucial in this field as they offer an approach to address common distributed computing problems. Examples of such problems include consensus, community detection, bit-dissemination or load-balancing problems. For such a reason, the study of network dynamics has applications in various fields, such as social and communication networks, swarm robotics and mobile agents, self-organization of distributed systems, and biological distributed algorithms. Additionally, the study of opinion dynamics is critical in understanding how information spreads in social networks, which can have significant implications for marketing, politics, and public opinion. The study of network dynamics is also related to the design analysis and implementation of distributed systems and networks.

The purpose of the workshop is to bring together researchers interested in studying network dynamics networks and to facilitate discussions about the strategies and techniques utilized for their analysis and design.

This workshop is colocated with DISC 2024 and aims at the general DISC audience.

Schedule

The workshop will take place at the Spanish Engineering Institute (Madrid, Spain) on November 1st 2024.

Program

09:00-9:45 Talk 1 Peter Kling: Distributed Oscillators and Clocks via Random Interactions

09:45-10:30 Talk 2 Joel Rybicki: Majority consensus in stochastic populations

10:30-11:00 Coffee Break

11:00-11.45 Talk 3 Philipp Czerner: Space Complexity of Population Protocols

11:45-12:30 Talk 4 Alexandre Nolin: Coloring a Mostly Forgotten Graph

Workshop ends.

The entire program is live-streamed at https://unibocconi-it.zoom.us/j/5706126823

Speakers

Short bio: Peter is an assistant professor in the Department of Informatics at the University of Hamburg. Peter studied mathematics and computer science at the University of Paderborn. His PhD was supervised by Friedhelm Meyer auf der Heide. Afterward, Peter worked as a postdoctoral researcher at the University of Pittsburgh with Kirk Pruhs and his research group. He then joint Petra Berenbrink at the Simon Fraser University before joining the University of Hamburg. Peter's research aims at exploring the fundamental properties and limits of algorithmic solutions to optimization and decision problems.

Title: Distributed Oscillators and Clocks via Random Interactions (slides)

Abstract: We study the dynamics of huge systems of very simple, autonomous agents under erratic communication. Such systems find applications in, for example, the study of chemical reaction networks, the analysis of opinion dynamics in social networks, or the deployment of sensor networks to track animal populations. The standard model assumes n agents, each modeled as a simple finite state machine. Agents interact in small groups that are composed of (typically) randomly chosen agents. Upon such an interaction, each agent updates its state according to a common transition function that maps its own state and that of its interaction partners to a new state. A major challenge in such models is to create synchronization primitives that leverage the randomized group selection to simulate some form of global signal, which allows agents to perform their respective roles in a timed fashion. We will outline the state of the art for such primitives and dive into recent constructions that seems particularly promising with respect to efficiency and provided synchronization guarantees.

Short bio: Joel Rybicki is an assistant professor at Humboldt University of Berlin. His research interests range from distributed algorithms to modelling biological dynamics. Previously, he was a postdoctoral fellow at the Institute of Science and Technology Austria (ISTA) and University of Helsinki, and he completed his doctorate in Aalto University.

Title: Majority consensus in stochastic populations (slides)

Abstract: Majority consensus is a basic signal amplification primitive in distributed systems. In this problem, the goal is to agree on the input value initially held by the majority of the individuals. In this talk, we discuss majority consensus dynamics based on competitive exclusion in microbial populations. Here, the system consists of two microbial species that follow stochastic population dynamics. We consider the following question: what is the probability that the system reaches a configuration consisting only of the species that initially had the higher count? We discuss how the answer to this question depends on the assumptions about the reproductive and competitive dynamics of the species.


Short bio: Philipp is a PhD student in computer science advised by Prof. Javier Esparza in the Chair for Foundations of Software Reliability and Theoretical Computer Science at Technical University of Munich. His research focuses on the theoretical analysis of weak models of distributed computing, in particular systems with stochastically interacting identical agents such as population protocols. 

Title: Space Complexity of Population Protocols (slides)

Abstract: In the population protocol model, a large number of finite-state agents interact stochastically in pairs, to collectively decide a global property of the population. Despite its simplicity, the model gives rise to rich dynamics that have been studied extensively in the literature. Recently, much progress has been made in the area of space complexity, investigating the fundamental question: for a given predicate, what is the smallest number of states of any protocol deciding this predicate? We discuss both upper and lower bounds that have been obtained in this area, as well as connections to robustness, i.e. protocols that resist failures of individual agents.

Short bio: Alexandre Nolin is currently a postdoctoral researcher at CISPA in the group of Sebastian Brandt. Before that, he received a Ph.D. in Computer Science at Université Paris Cité, where he was advised by Sophie Laplante, and was a postdoctoral researcher at Reykjavik University, where he was hosted by Magnús M. Halldórsson. His current research interests primarily gravitate around distributed graph algorithms. 

Title: Coloring a Mostly Forgotten Graph (slides)

Abstract: In recent years, results known as "palette sparsification" had implications for graph coloring problems in a diversity of algorithmic models. Such results are theorems of the form: (i) for each node v, let Ψ(v) be the set of colors that it is allowed to take (its "palette"); (ii) let each node v independently restrict itself to only use some random subset of its palette (this is the "sparsification"); then (iii), with high probability, the graph can still be colored with this random restriction in place. The specific results can vary in the graph family considered, the initial palettes of nodes, the size and distribution of the nodes' random subsampling, and the difficulty of finding a coloring post-"sparsification".

The appeal of such results is that the random palette restriction makes some edges non-constraining: where endpoints of an edge sample disjoint sets of colors. The catch, however, is that the random restrictions are constraints in themselves that might be hard to deal with. Also, in a distributed context, edges usually act both as constraints and communication links, and one might ask whether removing the constraint created by an edge also allows to forgo the communication link.

In this talk, we will explore this latter question, seeing that in fact, some graph coloring problems can be computed in some distributed settings while ignoring a large fraction of the communication links. Based on joint work with Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kuhn, and Tigran Tonoyan.

Organizers

Emilio Cruciani (University of Salzburg), Francesco D'Amore (Bocconi University), Isabella Ziccardi (Bocconi University)

Previous Editions

WAND 2023 (L'Aquila, Italy)