15 citations · 32 across the 12 of their papers we have counts for
20 papers
Counting in Population Protocols on Graphs
Petra Berenbrink, Robert Elsässer, Tom Friedetzky +3
We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph with nodes. In each step,…
(Almost) Perfect Discrete Iterative Load Balancing
Petra Berenbrink, Robert Elsässer, Tom Friedetzky +4
We consider discrete, iterative load balancing via matchings on arbitrary graphs. Initially each node holds a certain number of tokens, defining the load of the node, and the objec…
Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient
Petra Berenbrink, Robert Elsässer, Thorsten Götte +2
We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common…
Population Protocols for Exact Plurality Consensus -- How a small chance of failure helps to eliminate insignificant opinions
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier +4
We consider the \emph{exact plurality consensus} problem for \emph{population protocols}. Here, anonymous agents start each with one of opinions. Their goal is to agree on…
Dynamic Averaging Load Balancing on Arbitrary Graphs
Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour +2
In this paper we study dynamic averaging load balancing on general graphs. We consider infinite time and dynamic processes, where in every step new load items are assigned to rando…
On the Hierarchy of Distributed Majority Protocols
Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard +3
We study the Consensus problem among agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in whi…
Asynchronous Opinion Dynamics in Social Networks
Petra Berenbrink, Martin Hoefer, Dominik Kaaser +3
Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well…
Loosely-Stabilizing Phase Clocks and the Adaptive Majority Problem
Petra Berenbrink, Felix Biermeier, Christopher Hahn +1
We present a loosely-stabilizing phase clock for population protocols. In the population model we are given a system of identical agents which interact in a sequence of randoml…
Fast Consensus via the Unconstrained Undecided State Dynamics
Gregor Bankhamer, Petra Berenbrink, Felix Biermeier +4
We consider the plurality consensus problem among agents. Initially, each agent has one of different opinions. Agents choose random interaction partners and revise their st…
On Greedily Packing Anchored Rectangles
Christoph Damerius, Dominik Kaaser, Peter Kling +1
Consider a set P of points in the unit square U, one of them being the origin. For each point p in P you may draw a rectangle in U with its lower-left corner in p. What is the maxi…
Simulating Population Protocols in Sub-Constant Time per Interaction
Petra Berenbrink, David Hammer, Dominik Kaaser +3
We consider the problem of efficiently simulating population protocols. In the population model, we are given a distributed system of agents modeled as identical finite-state m…
On Counting the Population Size
Petra Berenbrink, Dominik Kaaser, Tomasz Radzik
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of identical agents which interact in pairs wi…
Simple Load Balancing
Petra Berenbrink, Tom Friedetzky, Dominik Kaaser +1
We consider the following load balancing process for tokens distributed arbitrarily among nodes connected by a complete graph: In each time step a pair of nodes is selected…
A population protocol for exact majority with stabilization time and asymptotically optimal number of states
Petra Berenbrink, Robert Elsässer, Tom Friedetzky +3
A population protocol can be viewed as a sequence of pairwise interactions of agents (nodes). During one interaction, two agents selected uniformly at random update their state…
Positive Aging Admits Fast Asynchronous Plurality Consensus
Gregor Bankhamer, Robert Elsässer, Dominik Kaaser +1
We study distributed plurality consensus among nodes, each of which initially holds one of opinions. The goal is to eventually agree on the initially dominant opinion. We c…
Time-space Trade-offs in Population Protocols for the Majority Problem
Petra Berenbrink, Robert Elsässer, Tom Friedetzky +3
Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of identical agents (finite state machines) performs a global…
Rapid Asynchronous Plurality Consensus
Robert Elsässer, Tom Friedetzky, Dominik Kaaser +2
We consider distributed plurality consensus in a complete graph of size with initial opinions. We design an efficient and simple protocol in the asynchronous communication…
On the Voting Time of the Deterministic Majority Process
Dominik Kaaser, Frederik Mallmann-Trenn, Emanuele Natale
In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, every node adopts the majority opinion…
Discrete Load Balancing in Heterogeneous Networks with a Focus on Second-Order Diffusion
Hoda Akbari, Petra Berenbrink, Robert Elsässer +1
In this paper we consider a wide class of discrete diffusion load balancing algorithms. The problem is defined as follows. We are given an interconnection network and a number of l…
On the Influence of Graph Density on Randomized Gossiping
Robert Elsässer, Dominik Kaaser
Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, the broadcasting problem, a message has to be spread among all no…