Staff profile

Personal webpage

• Probabilistic methods and algorithms
• Distributed algorithms

• ACiD: Algorithms and Complexity

Chapter in book

• Berenbrink, Petra, Elsässer, Robert, Friedetzky, Tom, Nagel, Lars & Sauerwald, Thomas (2011). Faster Coupon Collecting via Replication with Applications in Gossiping. In Mathematical Foundations of Computer Science 2011. 6907: 72-83.
• Berenbrink, Petra, Friedetzky, Tom, Hajirasouliha, Iman & Hu, Zengjian (2007). Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks. In Algorithms – ESA 2007. 4698: 41.
• Bebek, Gürkan, Berenbrink, Petra, Cooper, Colin, Friedetzky, Tom, Nadeau, Joseph H. & Sahinalp, S. Cenk (2006). Improved Duplication Models for Proteome Network Evolution. In Systems Biology and Regulatory Genomics. 4023: 119.
• Berenbrink, Petra, Ergun, Funda & Friedetzky, Tom (2005). Finding Frequent Patterns in a String in Sublinear Time. In Algorithms – ESA 2005. 3669: 746.
• Berenbrink, Petra, Friedetzky, Tom, Hu, Zengjian & Martin, Russell (2005). On Weighted Balls-into-Bins Games. In STACS 2005. 3404: 231.
• Berenbrink, Petra, Friedetzky, Tom & Martin, Russell (2005). Dynamic Diffusion Load Balancing. In Automata, Languages and Programming. 3580: 1386.
• Ṣahinalp, S. Cenk, Eichler, Evan, Goldberg, Paul, Berenbrink, Petra, Friedetzky, Tom & Ergun, Funda (2002). Statistical Identification of Uniformly Mutated Segments within Repeats. In Combinatorial Pattern Matching. 2373: 249.

Conference Paper

• Friedetzky, T., Kutner, D., Mertzios, G.B., Stewart, I.A. & Trehan, A. (2023), Payment scheduling in the Interval Debt Model, Lecture Notes in Computer Science 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023). Novy Smokovec, Slovakia, Springer.
• Berenbrink, Petra, Friedetzky, Tom, Hahn, Christopher, Hintze, Lukas, Kaaser, Dominik, Kling, Peter & Nagel, Lars (2021), Infinite Balanced Allocation via Finite Capacities, 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). Washington, DC / Virtual, IEEE, 965-975.
• Berenbrink, Petra, Friedetzky, Tom, Kaaser, Dominik & Kling, Peter (2019), Tight & Simple Load Balancing, IEEE International Parallel & Distributed Processing Symposium (IPDPS). Rio de Janeiro, Brazil, IEEE, 718-726.
• Berenbrink, Petra, Elsässer, Robert, Friedetzky, Tom, Kaaser, Dominik, Kling, Peter & Radzik, Tomasz (2018), A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states, in Schmid, Ulrich & Widder, Josef eds, Leibniz International Proceedings in Informatics (LIPIcs) 121: International Symposium on DIStributed Computing (DISC). New Orleans, USA, LIPICS, Dagstuhl, Germany, 10:1--10:18.
• Elsässer, Robert, Friedetzky, Tom, Kaaser, Dominik & Mallmann-Trenn, Frederik (2017), Brief Announcement: Rapid Asynchronous Plurality Consensus, ACM Symposium on Principles of Distributed Computing (PODC). Washington, DC, ACM, New York, NY, USA, 363-365.
• Berenbrink, Petra, Friedetzky, Tom, Kling, Peter, Mallmann-Trenn, Frederik & Wastell, Chris (2016), Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing, in Sankowski, Piotr & Zaroliagis, Christos eds, Leibniz International Proceedings in Informatics (LIPIcs) 57: 24th Annual European Symposium on Algorithms (ESA 2016). Aarhus, Denmark, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Dagstuhl, 10:1–10:18.
• Berenbrink, Petra, Friedetzky, Tom, Giakkoupis, George & Kling, Peter (2016), Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time, in Chatzigiannakis, Ioannis, Mitzenmacher, Michael, Rabani, Yuval & Sangiorgi, Davide eds, Leibniz International Proceedings in Informatics (LIPIcs) 55: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Rome, Italy, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Dagstuhl, 1-14.
• Berenbrink, Petra, Friedetzky, Tom, Kling, Peter, Mallmann-Trenn, Frederik, Nagel, Lars & Wastell, Chris (2016), Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins, ACM Symposium on Principles of Distributed Computing ACM Symposium on Principles of Distributed Computing - PODC '16. Chicago, Illinois, Association for Computing Machinery (ACM), New York, 83-92.
• Berenbrink, Petra, Friedetzky, Tom, Mallmann-Trenn, Frederik, Meshkinfamfard, Sepehr & Wastell, Chris (2015), Threshold Load Balancing with Weighted Tasks, Parallel and Distributed Processing Symposium (IPDPS) 2015 IEEE 29th International Parallel and Distributed Processing Symposium. Hyderabad, India, IEEE, Los Alamitos, 550-558.
• Berenbrink, Petra, Brinkmann, André, Elsässer, Robert, Friedetzky, Tom & Nagel, Lars (2015), Randomized Renaming in Shared Memory Systems, Parallel and Distributed Processing Symposium (IPDPS) 2015 IEEE 29th International Parallel and Distributed Processing Symposium. Hyderabad, India, IEEE, Los Alamitos, 542-549.
• Berenbrink, Petra, Brinkmann, Andre, Friedetzky, Tom, Meister, Dirk & Nagel, Lars (2013), Distributing Storage in Cloud Environments, 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum. 963-973.
• Berenbrink, Petra, Czumaj, Artur, Englert, Matthias, Friedetzky, Tom & Nagel, Lars (2012), Multiple-Choice Balanced Allocation in (Almost) Parallel, Lecture Notes in Computer Science 7408: APPROX/RANDOM 2012. Boston, USA, Springer, 411.
• Friedetzky, Tom, Gąsieniec, Leszek, Gorry, Thomas & Martin, Russel (2012), Observe and Remain Silent (Communication-Less Agent Location Discovery), Lecture Notes in Computer Science 7464: Mathematical Foundations of Computer Science 2012. Bratislava, Slovakia, Springer, 407-418.
• Brinkmann, Andre, Popov, Igor & Friedetzky, Tom (2012), On the Influence of PRNGs on Data Distribution, 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Munich, Germany, IEEE, 536-543.
• Berenbrink, Petra, Cooper, Colin & Friedetzky, Tom (2012), Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time, PODC '12 ACM Symposium on Principles of Distributed Computing - PODC '12. Madeira, Portugal, ACM, 29-36.
• Berenbrink, Petra, Cooper, Colin, Friedetzky, Tom, Friedrich, Tobias & Sauerwald, Thomas (2011), Randomized Diffusion for Indivisible Loads, in Randall, Dana eds, n/a: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco, Society for Industrial and Applied Mathematics, San Francisco CA, 429-439.
• Berenbrink, Petra, Brinkmann, Andre, Friedetzky, Tom & Nagel, Lars (2010), Balls into non-uniform bins, 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). 1.
• Berenbrink, Petra, Brinkmann, André, Friedetzky, Tom & Nagel, Lars (2010), Balls into bins with related random choices, Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10. 100.
• Dantchev, Stefan, Friedetzky, Tom & Nagel, Lars (2009), Sublinear-Time Algorithms for Tournament Graphs, in Ngo, H. Q. eds, Lecture Notes in Computer Science 5609: 15thAnnual International Conference of Computing and Combinatorics (COCOON 2009). Niagara Falls, New York, USA, Springer, Berlin Heidelberg, 459-471.
• Berenbrink, Petra, Elsaesser, Robert & Friedetzky, Tom (2008), Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing - PODC '08. 155.
• Berenbrink, P., Friedetzky, T. & Zengjian Hu, (2006), A new analytical method for parallel, diffusion-type load balancing, Proceedings 20th IEEE International Parallel & Distributed Processing Symposium.
• Berenbrink Petra Friedetzky, Tom, Goldberg, Leslie Ann, Goldberg, Paul W., Hu, Zengjian Hu & Martin, Russell A. (2006), Distributed selfish load balancing, ACM-SIAM Symposium on Discrete Algorithms. Miami, Florida, USA, ACM-SIAM, 354--363.
• Adler, Micah, Berenbrink, Petra, Friedetzky, Tom, Goldberg, Leslie Ann, Goldberg, Paul & Paterson, Mike (2003), A proportionate fair scheduling rule with good worst-case performance, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA '03. 101.
• Berenbrink, P., Friedetzky, T. & Goldberg, L.A. (2001), The natural work-stealing algorithm is stable, Proceedings 2001 IEEE International Conference on Foundations of Computer Science. 178.
• Berenbrink, Petra, Czumaj, Artur, Friedetzky, Tom & Vvedenskaya, Nikita D. (2000), Infinite parallel job allocation (extended abstract), Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA '00. 99.
• Berenbrink, Petra, Friedetzky, Tom & Steger, Angelika (1999), Randomized and adversarial load balancing, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99. 175.
• Berenbrink, Petra, Friedetzky, Tom & Mayr, Ernst W. (1998), Parallel continuous randomized load balancing (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA '98. 192.

Journal Article

• Berenbrink, Petra, Brinkmann, André, Elsässer, Robert, Friedetzky, Tom & Nagel, Lars (2021). Randomized renaming in shared memory systems. Journal of Parallel and Distributed Computing 150: 112-120.
• Berenbrink, Petra, Elsässer, Robert, Friedetzky, Tom, Kaaser, Dominik, Kling, Peter & Radzik, Tomasz (2021). Time-space trade-offs in population protocols for the majority problem. Distributed Computing 34(2): 91-111.
• Berenbrink, Petra, Friedetzky, Tom, Kling, Peter, Mallmann-Trenn, Frederik, Nagel, Lars & Wastell, Chris (2018). Self-Stabilizing Balls and Bins in Batches. Algorithmica 80(12): 3673-3703.
• Berenbrink, Petra, Friedetzky, Tom, Mallmann-Trenn, Frederik, Meshkinfamfard, Sepehr & Wastell, Chris (2018). Threshold Load Balancing With Weighted Tasks. Journal of Parallel and Distributed Computing 113: 218-226.
• Berenbrink, Petra, Elsässer, Robert & Friedetzky, Tom (2016). Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. Distributed Computing 29(5): 317-339.
• Berenbrink, P., Cooper, C. & Friedetzky, T. (2015). Random walks which prefer unvisited edges exploring high girth even degree expanders in linear time. Random Structures and Algorithms 46(1): 36-54.
• Berenbrink, Petra, Cooper, Colin, Friedetzky, Tom, Friedrich, Tobias & Sauerwald, Thomas (2015). Randomized diffusion for indivisible loads. Journal of Computer and System Sciences 81(1): 159-185.
• Miranda, Alberto, Effert, Sascha, Kang, Yangwook, Miller, Ethan L., Popov, Ivan, Brinkmann, Andre, Friedetzky, Tom & Cortes, Toni (2014). Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems. ACM Transactions on Storage 10(3): 9.
• Berenbrink, Petra, Brinkmann, André, Friedetzky, Tom & Nagel, Lars (2014). Balls into non-uniform bins. Journal of Parallel and Distributed Computing 74(2): 2065-2076.
• Berenbrink, Petra, Friedetzky, Tom, Hajirasouliha, Iman & Hu, Zengjian (2012). Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks. Algorithmica 62(3-4): 767-786.
• Berenbrink, Petra, Brinkmann, Andre, Friedetzky, Tom & Nagel, Lars (2012). Balls into bins with related random choices. Journal of Parallel and Distributed Computing 72(2): 246-253.
• Dantchev, Stefan, Friedetzky, Tom & Nagel, Lars (2010). Sublinear-time algorithms for tournament graphs. Journal of Combinatorial Optimization
• Berenbrink, Petra, Friedetzky, Tom & Hu, Zengjian (2009). A New Analytical Method for Parallel, Diffusion-type Load Balancing. Journal of Parallel and Distributed Computing (JPDC) 69(1): 54-61.
• Berenbrink, Petra, Friedetzky, Tom & Martin, Russell (2008). On the Stability of Dynamic Diffusion Load Balancing. Algorithmica 50(3): 329-350.
• Berenbrink, Petra, Friedetzky, Tom, Hu, Zengjian & Martin, Russell (2008). On weighted balls-into-bins games. Theoretical Computer Science 409(3): 511.
• Berenbrink, Petra, Friedetzky, Tom, Goldberg, Leslie Ann, Goldberg, Paul W., Hu, Zengjian & Martin, Russell (2007). Distributed Selfish Load Balancing. SIAM Journal on Computing 37(4): 1163.
• Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J. & Sahinalp, S.C. (2006). The degree distribution of the generalized duplication model. Theoretical Computer Science 369(1-3): 239.
• BERENBRINK, PETRA, FRIEDETZKY, THOMAS, MAŇUCH, JÁN & STACHO, LADISLAV (2005). (QUASI) SPANNERS FOR MOBILE AD HOC NETWORKS. Journal of Interconnection Networks 06(02): 63.
• SAHINALP, S. CENK, EICHLER, EVAN, GOLDBERG, PAUL, BERENBRINK, PETRA, FRIEDETZKY, TOM & ERGUN, FUNDA (2004). IDENTIFYING UNIFORMLY MUTATED SEGMENTS WITHIN REPEATS. Journal of Bioinformatics and Computational Biology 02(04): 657.
• Berenbrink, P., Friedetzky, T. & Goldberg, L. A. (2003). The natural work-stealing algorithm is stable. SIAM Journal on Computing 32(5): 1260-1279.