8 papers
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…
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…