15 citations · 31 across the 12 of their papers we have counts for
13 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…
Balls and Bins and the Infinite Process with Random Deletions
Petra Berenbrink, Tom Friedetzky, Peter Kling +1
We consider an infinite balls-into-bins process with deletions where in each discrete step a coin is tossed as to whether, with probability , a new ball is allo…
A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols
Henry Austin, Petra Berenbrink, Tom Friedetzky +2
We consider the problem of self-stabilizing leader election in the population model by Angluin, Aspnes, Diamadi, Fischer, and Peralta (JDistComp '06). The population model is a wel…
Payment Scheduling in the Interval Debt Model
Tom Friedetzky, David C. Kutner, George B. Mertzios +2
The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We cons…
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…
Plurality Consensus via Shuffling: Lessons Learned from Load Balancing
Petra Berenbrink, Tom Friedetzky, Peter Kling +2
We consider \emph{plurality consensus} in a network of nodes. Initially, each node has one of opinions. The nodes execute a (randomized) distributed protocol to agree on th…
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…
Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time
Petra Berenbrink, Colin Cooper, Tom Friedetzky
We consider a modified random walk which uses unvisited edges whenever possible, and makes a simple random walk otherwise. We call such a walk an edge-process. We assume there is a…
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…