Petra Berenbrink

According to our database, Petra Berenbrink authored at least 102 papers between 1996 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Asynchronous opinion dynamics in social networks.

Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Pascal Lenzner, Malin Rau, Daniel Schmand

Distributed Comput., September, 2024

WalkSAT is linear on random 2-SAT.

Petra Berenbrink, Amin Coja-Oghlan, Colin Cooper, Thorsten Götte, Lukas Hintze, Pavel Zakharov

CoRR, 2024

Undecided State Dynamics with Stubborn Agents.

Petra Berenbrink, Felix Biermeier, Christopher Hahn

CoRR, 2024

2023

Inference of a rumor's source in the independent cascade model.

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg, Malin Rau

Proceedings of the Uncertainty in Artificial Intelligence, 2023

Distributed Averaging in Opinion Dynamics.

Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik, Nicolas Rivera

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model.

Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, John Lazarsfeld

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Dynamic Averaging Load Balancing on Arbitrary Graphs.

Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser, Malin Rau

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Distributed Averaging in Population Protocols.

Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Nicolás Rivera, Tomasz Radzik

CoRR, 2022

On early extinction and the effect of travelling in the SIR model.

Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik

Proceedings of the Uncertainty in Artificial Intelligence, 2022

Fast Consensus via the Unconstrained Undecided State Dynamics.

Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem.

Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser

Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks, 2022

Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions.

Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, Peter Kling

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

On the Hierarchy of Distributed Majority Protocols.

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, Malin Rau

Proceedings of the 26th International Conference on Principles of Distributed Systems, 2022

On the Optimality of the Greedy Garbage Collection Strategy for SSDs.

Ernst Althaus, Petra Berenbrink, André Brinkmann, Rebecca Steiner

Proceedings of the 42nd IEEE International Conference on Distributed Computing Systems, 2022

2021

Introduction to the Special Issue for SPAA 2019.

Petra Berenbrink

ACM Trans. Parallel Comput., 2021

Randomized renaming in shared memory systems.

Petra Berenbrink, André Brinkmann, Robert Elsässer, Tom Friedetzky, Lars Nagel

J. Parallel Distributed Comput., 2021

Time-space trade-offs in population protocols for the majority problem.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik

Distributed Comput., 2021

Self-Stabilizing Phase Clocks and the Adaptive Majority Problem.

Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser

CoRR, 2021

Infinite Balanced Allocation via Finite Capacities.

Petra Berenbrink, Tom Friedetzky, Christopher Hahn, Lukas Hintze, Dominik Kaaser, Peter Kling, Lars Nagel

Proceedings of the 41st IEEE International Conference on Distributed Computing Systems, 2021

2020

Optimal time and space leader election in population protocols.

Petra Berenbrink, George Giakkoupis, Peter Kling

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Brief Announcement: Optimal Time and Space Leader Election in Population Protocols.

Petra Berenbrink, George Giakkoupis, Peter Kling

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Simulating Population Protocols in Sub-Constant Time per Interaction.

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, Hung Tran

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Improved Analysis of Deterministic Load-Balancing Schemes.

Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemyslaw Uznanski

ACM Trans. Algorithms, 2019

On Counting the Population Size.

Petra Berenbrink, Dominik Kaaser, Tomasz Radzik

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Tight & Simple Load Balancing.

Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, Peter Kling

Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium, 2019

2018

Threshold load balancing with weighted tasks.

Petra Berenbrink, Tom Friedetzky, Frederik Mallmann-Trenn, Sepehr Meshkinfamfard, Chris Wastell

J. Parallel Distributed Comput., 2018

Simple Load Balancing.

Petra Berenbrink, Tom Friedetzky, Dominik Kaaser, Peter Kling

CoRR, 2018

A population protocol for exact majority with O(\log^5/3n) stabilization time and asymptotically optimal number of states.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik

CoRR, 2018

Majority & Stabilization in Population Protocols.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik

CoRR, 2018

Self-Stabilizing Balls and Bins in Batches - The Power of Leaky Bins.

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Chris Wastell

Algorithmica, 2018

A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, Tomasz Radzik

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Simple and Efficient Leader Election.

Petra Berenbrink, Dominik Kaaser, Peter Kling, Lena Otterbach

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

Tight Bounds for Coalescing-Branching Random Walks on Regular Graphs.

Petra Berenbrink, George Giakkoupis, Peter Kling

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Ignore or Comply?: On Breaking Symmetry in Consensus.

Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, Emanuele Natale

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Tight Load Balancing Via Randomized Local Search.

Petra Berenbrink, Peter Kling, Christopher Liaw, Abbas Mehrabian

Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium, 2017

2016

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky

Distributed Comput., 2016

A simple approach for adapting continuous load balancing processes to discrete settings.

Hoda Akbari, Petra Berenbrink, Thomas Sauerwald

Distributed Comput., 2016

Concurrent imitation dynamics in congestion games.

Heiner Ackermann, Petra Berenbrink, Simon Fischer, Martin Hoefer

Distributed Comput., 2016

Plurality Consensus via Shuffling: Lessons Learned from Load Balancing.

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Chris Wastell

CoRR, 2016

Self-stabilizing Balls & Bins in Batches.

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Chris Wastell

CoRR, 2016

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract].

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Christopher Wastell

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Bounds on the Voter Model in Dynamic Networks.

Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, Frederik Mallmann-Trenn

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time.

Petra Berenbrink, Tom Friedetzky, George Giakkoupis, Peter Kling

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing.

Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Chris Wastell

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time.

Petra Berenbrink, Colin Cooper, Tom Friedetzky

Random Struct. Algorithms, 2015

Randomized diffusion for indivisible loads.

Petra Berenbrink, Colin Cooper, Tom Friedetzky, Tobias Friedrich, Thomas Sauerwald

J. Comput. Syst. Sci., 2015

Communication Complexity of Quasirandom Rumor Spreading.

Petra Berenbrink, Robert Elsässer, Thomas Sauerwald

Algorithmica, 2015

Discrete Load Balancing in Heterogeneous Networks with a Focus on Second-Order Diffusion.

Hoda Akbari, Petra Berenbrink, Robert Elsässer, Dominik Kaaser

Proceedings of the 35th IEEE International Conference on Distributed Computing Systems, 2015

2014

Randomised broadcasting: Memory vs. randomness.

Petra Berenbrink, Robert Elsässer, Thomas Sauerwald

Theor. Comput. Sci., 2014

Distributed Selfish Load Balancing on Networks.

Petra Berenbrink, Martin Hoefer, Thomas Sauerwald

ACM Trans. Algorithms, 2014

Balls into non-uniform bins.

Petra Berenbrink, André Brinkmann, Tom Friedetzky, Lars Nagel

J. Parallel Distributed Comput., 2014

Estimating the number of connected components in sublinear time.

Petra Berenbrink, Bruce Krayenhoff, Frederik Mallmann-Trenn

Inf. Process. Lett., 2014

Be Fair and Be Selfish! Characterizing Deterministic Diffusive Load-Balancing Schemes with Small Discrepancy.

Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemyslaw Uznanski

CoRR, 2014

Palindrome Recognition In The Streaming Model.

Petra Berenbrink, Funda Ergün, Frederik Mallmann-Trenn, Erfan Sadeqi Azer

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013

Balls-into-bins with nearly optimal load distribution.

Petra Berenbrink, Kamyar Khodamoradi, Thomas Sauerwald, Alexandre Stauffer

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Parallel rotor walks on finite graphs and applications in discrete load balancing.

Hoda Akbari, Petra Berenbrink

Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, 2013

Distributing Storage in Cloud Environments.

Petra Berenbrink, André Brinkmann, Tom Friedetzky, Dirk Meister, Lars Nagel

Proceedings of the 2013 IEEE International Symposium on Parallel & Distributed Processing, 2013

2012

Balls into bins with related random choices.

Petra Berenbrink, André Brinkmann, Tom Friedetzky, Lars Nagel

J. Parallel Distributed Comput., 2012

Chains-into-bins processes.

Tugkan Batu, Petra Berenbrink, Colin Cooper

J. Discrete Algorithms, 2012

Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks.

Petra Berenbrink, Tom Friedetzky, Iman Hajirasouliha, Zengjian Hu

Algorithmica, 2012

Distributed selfish load balancing with weights and speeds.

Clemens P. J. Adolphs, Petra Berenbrink

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Improved Bounds for Discrete Diffusive Load Balancing.

Clemens P. J. Adolphs, Petra Berenbrink

Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium, 2012

Multiple-Choice Balanced Allocation in (Almost) Parallel.

Petra Berenbrink, Artur Czumaj, Matthias Englert, Tom Friedetzky, Lars Nagel

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Faster Coupon Collecting via Replication with Applications in Gossiping.

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Lars Nagel, Thomas Sauerwald

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Evolutionary equilibrium in Bayesian routing games: Specialization and niche formation.

Petra Berenbrink, Oliver Schulte

Theor. Comput. Sci., 2010

Speeding Up Random Walks with Neighborhood Exploration.

Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik, Thomas Sauerwald

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Efficient Information Exchange in the Random Phone-Call Model.

Petra Berenbrink, Jurek Czyzowicz, Robert Elsässer, Leszek Gasieniec

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Energy efficient randomised communication in unknown AdHoc networks.

Petra Berenbrink, Colin Cooper, Zengjian Hu

Theor. Comput. Sci., 2009

A sublinear-time approximation scheme for bin packing.

Tugkan Batu, Petra Berenbrink, Christian Sohler

Theor. Comput. Sci., 2009

A new analytical method for parallel, diffusion-type load balancing.

Petra Berenbrink, Tom Friedetzky, Zengjian Hu

J. Parallel Distributed Comput., 2009

The Weighted Coupon Collector's Problem and Applications.

Petra Berenbrink, Thomas Sauerwald

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

On weighted balls-into-bins games.

Petra Berenbrink, Tom Friedetzky, Zengjian Hu, Russell A. Martin

Theor. Comput. Sci., 2008

On the Stability of Dynamic Diffusion Load Balancing.

Petra Berenbrink, Tom Friedetzky, Russell A. Martin

Algorithmica, 2008

2007

Distributed Selfish Load Balancing.

Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin

SIAM J. Comput., 2007

Not All Scale-Free Networks Are Born Equal: The Role of the Seed Graph in PPI Network Evolution.

Fereydoun Hormozdiari, Petra Berenbrink, Natasa Przulj, Süleyman Cenk Sahinalp

PLoS Comput. Biol., 2007

2006

The degree distribution of the generalized duplication model.

Gürkan Bebek, Petra Berenbrink, Colin Cooper, Tom Friedetzky, Joseph H. Nadeau, Süleyman Cenk Sahinalp

Theor. Comput. Sci., 2006

Balanced Allocations: The Heavily Loaded Case.

Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking

SIAM J. Comput., 2006

Utilitarian resource assignment.

Petra Berenbrink, Leslie Ann Goldberg, Paul W. Goldberg, Russell A. Martin

J. Discrete Algorithms, 2006

Energy Efficient Randomized Communication in Unknown AdHoc Networks

Petra Berenbrink, Colin Cooper, Zengjian Hu

CoRR, 2006

Not All Scale Free Networks Are Born Equal: The Role of the Seed Graph in PPI Network Emulation.

Fereydoun Hormozdiari, Petra Berenbrink, Natasa Przulj, Süleyman Cenk Sahinalp

Proceedings of the Systems Biology and Computational Proteomics, 2006

2005

(quasi) Spanners for Mobile Ad Hoc Networks.

Petra Berenbrink, Tom Friedetzky, Ján Manuch, Ladislav Stacho

J. Interconnect. Networks, 2005

Improved Duplication Models for Proteome Network Evolution.

Gürkan Bebek, Petra Berenbrink, Colin Cooper, Tom Friedetzky, Joseph H. Nadeau, Süleyman Cenk Sahinalp

Proceedings of the Systems Biology and Regulatory Genomics, 2005

Dynamic Diffusion Load Balancing.

Petra Berenbrink, Tom Friedetzky, Russell A. Martin

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Finding Frequent Patterns in a String in Sublinear Time.

Petra Berenbrink, Funda Ergün, Tom Friedetzky

Proceedings of the Algorithms, 2005

2004

Identifying Uniformly Mutated Segments within Repeats.

Süleyman Cenk Sahinalp, Evan E. Eichler, Paul W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergün

J. Bioinform. Comput. Biol., 2004

2003

The Natural Work-Stealing Algorithm is Stable.

Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg

SIAM J. Comput., 2003

A proportionate fair scheduling rule with good worst-case performance.

Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Mike Paterson

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

2002

Statistical Identification of Uniformly Mutated Segments within Repeats.

Süleyman Cenk Sahinalp, Evan E. Eichler, Paul W. Goldberg, Petra Berenbrink, Tom Friedetzky, Funda Ergün

Proceedings of the Combinatorial Pattern Matching, 13th Annual Symposium, 2002

2001

SIMLAB-A Simulation Environment for Storage Area Networks.

Petra Berenbrink, André Brinkmann, Christian Scheideler

Proceedings of the Ninth Euromicro Workshop on Parallel and Distributed Processing, 2001

Simple Routing Strategies for Adversarial Systems.

Baruch Awerbuch, Petra Berenbrink, André Brinkmann, Christian Scheideler

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Randomized allocation of independent tasks.

Petra Berenbrink

PhD thesis, 2000

Infinite parallel job allocation (extended abstract).

Petra Berenbrink, Artur Czumaj, Tom Friedetzky, Nikita D. Vvedenskaya

Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

Distributed Path Selection for Storage Networks.

Petra Berenbrink, André Brinkmann, Christian Scheideler

Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2000

1999

Allocating Weighted Jobs in Parallel.

Petra Berenbrink, Friedhelm Meyer auf der Heide, Klaus Schröder

Theory Comput. Syst., 1999

Simple Competitive Request Scheduling Strategies.

Petra Berenbrink, Marco Riedel, Christian Scheideler

Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999

Randomized and Adversarial Load Balancing.

Petra Berenbrink, Tom Friedetzky, Angelika Steger

Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999

Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths.

Petra Berenbrink, Christian Scheideler

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Parallel Continuous Randomized Load Balancing (Extended Abstract).

Petra Berenbrink, Tom Friedetzky, Ernst W. Mayr

Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998

Analyzing an Infinite Parallel Job Allocation Process.

Micah Adler, Petra Berenbrink, Klaus Schröder

Proceedings of the Algorithms, 1998

1997

A Simple Distributed Scheduling Policy for Parallel Interactive Continuous Media Servers.

Valentin Rottmann, Petra Berenbrink, Reinhard Lüling

Parallel Comput., 1997

Online Scheduling of Continuous Media Streams.

Burkhard Monien, Petra Berenbrink, Reinhard Lüling, Marco Riedel

Proceedings of the Foundations of Computer Science: Potential - Theory, 1997

1996

Fault-Tolerant Shared Memory Simulations.

Petra Berenbrink, Friedhelm Meyer auf der Heide, Volker Stemann

Proceedings of the STACS 96, 1996