4 papers · 1 filter
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 all…
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…