1 citations · 1 across the 6 of their papers we have counts for
7 papers
The Voter Model with Opinion Graph
Petra Berenbrink, Thorsten Götte, Martin Hoefer +1
We study the \emph{voter model with opinion graph}, a generalization of the standard (pull) voter model that adds a notion of bounded confidence. In this process, we consider a fin…
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,…
Discrete Incremental Voting: New Bounds for General Graphs and Expanders
Petra Berenbrink, Colin Cooper, Thorsten Götte +2
We analyze the discrete incremental voting process (DIV) introduced by Cooper, Radzik, and Shiraga [OPODIS '23]. In this process, we consider a set of nodes connected in an…
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…
Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient
Petra Berenbrink, Robert Elsässer, Thorsten Götte +2
We present a silent, self-stabilizing ranking protocol for the population protocol model of distributed computing, where agents interact in randomly chosen pairs to solve a common…
WalkSAT is linear on random 2-SAT
Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper +3
In an influential article Papadimitriou [FOCS 1991] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with variables in $…
Undecided State Dynamics with Stubborn Agents
Petra Berenbrink, Felix Biermeier, Christopher Hahn
In the classical Approximate Majority problem with two opinions there are agents with Opinion 1 and with Opinion 2. The goal is to reach consensus and to agree on the majority opin…