2 papers
cs.DC2025
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…
math.CO2024
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 $…