🪄 Workshop on Analysis of Network Dynamics 🪄

Sparse Temporal Spanners with Low Stretch (slides)

A temporal graph is an undirected graph G=(V,E) along with a function that assigns a time-label to each edge in E.

A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., number of edges) of a temporal path from u to v. A temporal alpha-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V, up to a multiplicative stretch factor of alpha. The size of H is measured as the number of its edges.

We show that temporal cliques always admit a temporal (2k-1)-spanner with O( k n^(1+1/k) polylog(n) ) edges, where k>1 is an integer parameter of choice. Choosing k=log n, we obtain a temporal O(log n)-spanner with O(n log^2 n) edges which has almost the same size (up to a logarithmic factor) of the temporal spanner given in [Casteigts et al., JCSS 2021] that only preserves temporal connectivity.

We then turn our attention to general temporal graphs.  Since Ω(n^2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that O(n  polylog(n) / log(1 + epsilon) ) edges suffice to obtain a stretch of 1+epsilon, for any small epsilon > 0. This result is essentially tight in the following sense: there are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use  Ω(n^2) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of O(n^2 polylog(n) / beta) on the size of any temporal beta-additive spanner, which we show to be tight up to polylogarithmic factors.

Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.

Fast Plurality Consensus in the Gossip and Population Protocol Model

We consider the plurality consensus problem among n agents. Initially, each agent has one of k different opinions. Agents choose random interaction partners and revise their state according to a fixed transition function, depending on their own state and the state of the interaction partners. The goal is to reach a consensus configuration in which all agents agree on the same opinion, and if there is initially a sufficiently large bias towards one opinion, that opinion should prevail.

First, we analyze a synchronized variant of the undecided state dynamics defined as follows. The agents act in phases, consisting of a decision and a boosting part. In the decision part, any agent that encounters an agent with a different opinion becomes undecided. In the boosting part, undecided agents adopt the first opinion they encounter. We consider this dynamics in the population model and the gossip model, and show that the synchronized variant of the undecided state dynamics reaches consensus (w.h.p.) in (parallel) time O(log² n), independently of the initial number, bias, or distribution of opinions.

Then, we consider exact plurality consensus in the population model. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1. We present efficient protocols for exact plurality consensus, which allow for a small failure probability. These protocols beat the lower bounds, which have been derived for protocols that are always correct, i.e., they always converge toward the initially largest opinion.

This is joint work with Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling.

Biased and Context-Dependent Opinion Dynamics (slides)

In this talk, I will discuss opinion dynamics in multi-agent networks when a bias toward one of two possible opinions exists, for example reflecting a status quo versus a superior alternative.

To begin, I will consider a very simple model in which one agent is selected uniformly at random in every step, adopting the superior opinion with some fixed probability, and following some opinion update rule with remaining probability. While such a model is guaranteed to converge to the unique equilibrium in which all nodes share the superior opinion, the convergence of the process strongly depends on a non-obvious interplay between topology and underlying update rule.

If time suffices, I will further discuss recent directions at the intersection between voter models and dynamics of natural selection.

Local averaging in distributed networks and hoping for the best

In this talk we look at the setting where nodes in a network have an initial value and in every time step pick one random neighbour and average. We consider how the average changes over time when the averaging is done unidirectionally (only one node updates its value) and how it changes when some noise is added to every value sent.   

The Self-stabilizing Bit-Dissemination Problem (slides)

Effectively and reliably disseminating information is a fundamental task in numerous distributed systems, including the animal world. This challenge becomes particularly hard in scenarios where communication is noisy and constrained, where informed and uninformed agents are indistinguishable, and where the system is initially disorganized. The "Bit-Dissemination" problem was introduced to capture this challenge in an idealized setting. In this presentation, I will introduce this problem and describe several elegant protocols that have been devised to solve it. I will also present some impossibility results, illustrating how computational tools can be used to better understand the algorithmic constraints that exist within biological systems.