5 papers
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…
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…
Self-stabilizing Balls & Bins in Batches
Petra Berenbrink, Tom Friedetzky, Peter Kling +3
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled…
Distributed Selfish Load Balancing
Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg +3
Suppose that a set of tasks are to be shared as equally as possible amongst a set of resources. A game-theoretic mechanism to find a suitable allocation is to associate eac…