1 citations · 2 across the 4 of their papers we have counts for
5 papers
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…
Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes
Max Hahn-Klimroth, Dominik Kaaser, Malin Rau
In the pooled data problem we are given agents with hidden state bits, either or . The hidden states are unknown and can be seen as the underlying ground truth . To u…
Fast Convergence of -Opinion Undecided State Dynamics in the Population Protocol Model
Talley Amir, James Aspnes, Petra Berenbrink +4
We analyze the convergence of the -opinion Undecided State Dynamics (USD) in the population protocol model. For =2 opinions it is well known that the USD reaches consensus wi…
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…