Staff profile

Personal webpage

• Distributed algorithms
• Probabilistic methods and algorithms

Chapter in book

• Faster Coupon Collecting via Replication with Applications in Gossiping
  
  Berenbrink, P., Elsässer, R., Friedetzky, T., Nagel, L., & Sauerwald, T. (2011). Faster Coupon Collecting via Replication with Applications in Gossiping. In Mathematical Foundations of Computer Science 2011 (pp. 72-83). https://doi.org/10.1007/978-3-642-22993-0_10
• Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
  
  Berenbrink, P., Friedetzky, T., Hajirasouliha, I., & Hu, Z. (2007). Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks. In Algorithms – ESA 2007. https://doi.org/10.1007/978-3-540-75520-3_6
• Improved Duplication Models for Proteome Network Evolution
  
  Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J. H., & Sahinalp, S. C. (2006). Improved Duplication Models for Proteome Network Evolution. In Systems Biology and Regulatory Genomics. https://doi.org/10.1007/978-3-540-48540-7_11
• On Weighted Balls-into-Bins Games
  
  Berenbrink, P., Friedetzky, T., Hu, Z., & Martin, R. (2005). On Weighted Balls-into-Bins Games. In STACS 2005. https://doi.org/10.1007/978-3-540-31856-9_19
• Statistical Identification of Uniformly Mutated Segments within Repeats
  
  Ṣahinalp, S. C., Eichler, E., Goldberg, P., Berenbrink, P., Friedetzky, T., & Ergun, F. (2002). Statistical Identification of Uniformly Mutated Segments within Repeats. In Combinatorial Pattern Matching. https://doi.org/10.1007/3-540-45452-7_21

Conference Paper

• A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols
  
  Austin, H., Berenbrink, P., Friedetzky, T., Götte, T., & Hintze, L. (in press). A Space-Time Trade-off for Fast Self-Stabilizing Leader Election in Population Protocols. Presented at ACM Symposium on Principles of Distributed Computing (PODC’25), Huatulco, Mexico.
• Payment scheduling in the Interval Debt Model
  
  Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. In Lecture Notes in Computer Science (pp. 267-282). Springer Verlag. https://doi.org/10.1007/978-3-031-23101-8_18
• Infinite Balanced Allocation via Finite Capacities
  
  Berenbrink, P., Friedetzky, T., Hahn, C., Hintze, L., Kaaser, D., Kling, P., & Nagel, L. (2021). Infinite Balanced Allocation via Finite Capacities. Presented at 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), Washington, DC / Virtual. https://doi.org/10.1109/icdcs51616.2021.00096
• Tight & Simple Load Balancing
  
  Berenbrink, P., Friedetzky, T., Kaaser, D., & Kling, P. (2019). Tight & Simple Load Balancing. In 33rd IEEE International Parallel & Distributed Processing Symposium ; proceedings. (pp. 718-726). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ipdps.2019.00080
• A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states
  
  Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2018). A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. In U. Schmid & J. Widder (Eds.), 32nd International Symposium on Distributed Computing (DISC 2018). (pp. 10:1-10:18). LIPICS. https://doi.org/10.4230/lipics.disc.2018.10
• Brief Announcement: Rapid Asynchronous Plurality Consensus
  
  Elsässer, R., Friedetzky, T., Kaaser, D., & Mallmann-Trenn, F. (2017). Brief Announcement: Rapid Asynchronous Plurality Consensus. In Proceedings of ACM Symposium on Principles of Distributed Computing (PODC ’17) : Washington, DC, USA — July 25 - 27, 2017. (pp. 363-365). ACM. https://doi.org/10.1145/3087801.3087860
• Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing
  
  Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., & Wastell, C. (2016). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. In P. Sankowski & C. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms (ESA 2016). (pp. 1-18). Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.esa.2016.10
• Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time
  
  Berenbrink, P., Friedetzky, T., Giakkoupis, G., & Kling, P. (2016). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). (pp. 1-14). Schloss Dagstuhl, Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2016.136
• Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins
  
  Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2016). Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. (pp. 83-92). Association for Computing Machinery (ACM). https://doi.org/10.1145/2933057.2933092
• Randomized Renaming in Shared Memory Systems
  
  Berenbrink, P., Brinkmann, A., Elsässer, R., Friedetzky, T., & Nagel, L. (2015). Randomized Renaming in Shared Memory Systems. In 2015 IEEE 29th International Parallel and Distributed Processing Symposium (IPDPS 2015), 25–29 May 2015, Hyderabad, India ; proceedings. (pp. 542-549). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ipdps.2015.77
• Threshold Load Balancing with Weighted Tasks
  
  Berenbrink, P., Friedetzky, T., Mallmann-Trenn, F., Meshkinfamfard, S., & Wastell, C. (2015). Threshold Load Balancing with Weighted Tasks. In 2015 IEEE International Parallel and Distributed Processing Symposium (IPDPS 2015), 25–29 May 2015, Hyderabad, India ; proceedings. (pp. 550-558). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ipdps.2015.73
• Distributing Storage in Cloud Environments
  
  Berenbrink, P., Brinkmann, A., Friedetzky, T., Meister, D., & Nagel, L. (2013). Distributing Storage in Cloud Environments. Presented at 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum. https://doi.org/10.1109/ipdpsw.2013.148
• Observe and Remain Silent (Communication-Less Agent Location Discovery)
  
  Friedetzky, T., Gąsieniec, L., Gorry, T., & Martin, R. (2012). Observe and Remain Silent (Communication-Less Agent Location Discovery). In Mathematical Foundations of Computer Science 2012 (pp. 407-418). Springer Verlag. https://doi.org/10.1007/978-3-642-32589-2_37
• Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time
  
  Berenbrink, P., Cooper, C., & Friedetzky, T. (2012). Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (pp. 29-36). ACM. https://doi.org/10.1145/2332432.2332438
• On the Influence of PRNGs on Data Distribution
  
  Brinkmann, A., Popov, I., & Friedetzky, T. (2012). On the Influence of PRNGs on Data Distribution. In 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing (pp. 536-543). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/pdp.2012.58
• Multiple-Choice Balanced Allocation in (Almost) Parallel
  
  Berenbrink, P., Czumaj, A., Englert, M., Friedetzky, T., & Nagel, L. (2012). Multiple-Choice Balanced Allocation in (Almost) Parallel. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012. Springer Verlag. https://doi.org/10.1007/978-3-642-32512-0_35
• Randomized Diffusion for Indivisible Loads
  
  Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2011). Randomized Diffusion for Indivisible Loads. In D. Randall (Ed.), Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011. (pp. 429-439). Society for Industrial and Applied Mathematics.
• Balls into non-uniform bins
  
  Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010). Balls into non-uniform bins. Presented at 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). https://doi.org/10.1109/ipdps.2010.5470355
• Balls into bins with related random choices
  
  Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010). Balls into bins with related random choices. Presented at Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA ’10. https://doi.org/10.1145/1810479.1810500
• Sublinear-Time Algorithms for Tournament Graphs
  
  Dantchev, S., Friedetzky, T., & Nagel, L. (2009). Sublinear-Time Algorithms for Tournament Graphs. In H. Q. Ngo (Ed.), Computing and combinatorics : 15th Annual International Conference, COCOON 2009, 13-15 July 2009, Niagara Falls, NY, USA ; proceedings. (pp. 459-471). Springer Verlag. https://doi.org/10.1007/978-3-642-02882-3_46
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
  
  Berenbrink, P., Elsaesser, R., & Friedetzky, T. (2008). Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. Presented at Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing - PODC ’08. https://doi.org/10.1145/1400751.1400773
• A new analytical method for parallel, diffusion-type load balancing
  
  Berenbrink, P., Friedetzky, T., & Hu, Z. (2006). A new analytical method for parallel, diffusion-type load balancing. Presented at Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. https://doi.org/10.1109/ipdps.2006.1639292
• Dynamic diffusion load balancing
  
  Berenbrink, P., Friedetzky, T., & Martin, R. (2005). Dynamic diffusion load balancing. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, & M. Yung (Eds.), Automata, languages and programming : 32nd International Colloquium, ICALP 2005, 11-15 July 2005, Lisbon, Portugal ; proceedings (pp. 1386-1398). Springer Verlag. https://doi.org/10.1007/11523468_112
• Finding Frequent Patterns in a String in Sublinear Time
  
  Berenbrink, P., Ergun, F., & Friedetzky, T. (2005). Finding Frequent Patterns in a String in Sublinear Time. In Algorithms – ESA 2005 (pp. 746-757). Springer Verlag. https://doi.org/10.1007/11561071_66
• A proportionate fair scheduling rule with good worst-case performance
  
  Adler, M., Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P., & Paterson, M. (2003). A proportionate fair scheduling rule with good worst-case performance. Presented at Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures - SPAA ’03. https://doi.org/10.1145/777412.777430
• The natural work-stealing algorithm is stable
  
  Berenbrink, P., Friedetzky, T., & Goldberg, L. (2001). The natural work-stealing algorithm is stable. Presented at Proceedings 2001 IEEE International Conference on Foundations of Computer Science. https://doi.org/10.1109/sfcs.2001.959892
• Infinite parallel job allocation (extended abstract)
  
  Berenbrink, P., Czumaj, A., Friedetzky, T., & Vvedenskaya, N. D. (2000). Infinite parallel job allocation (extended abstract). Presented at Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA ’00. https://doi.org/10.1145/341800.341813
• Randomized and adversarial load balancing
  
  Berenbrink, P., Friedetzky, T., & Steger, A. (1999). Randomized and adversarial load balancing. Presented at Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA ’99. https://doi.org/10.1145/305619.305638
• Parallel continuous randomized load balancing (extended abstract)
  
  Berenbrink, P., Friedetzky, T., & Mayr, E. W. (1998). Parallel continuous randomized load balancing (extended abstract). Presented at Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA ’98. https://doi.org/10.1145/277651.277685

Journal Article

• Payment Scheduling in the Interval Debt Model
  
  Stewart, I., Kutner, D., Friedetzky, T., Trehan, A., & Mertzios, G. (2025). Payment Scheduling in the Interval Debt Model. Theoretical Computer Science, 1028, Article 115028. https://doi.org/10.1016/j.tcs.2024.115028
• Randomized renaming in shared memory systems
  
  Berenbrink, P., Brinkmann, A., Elsässer, R., Friedetzky, T., & Nagel, L. (2021). Randomized renaming in shared memory systems. Journal of Parallel and Distributed Computing, 150, 112-120. https://doi.org/10.1016/j.jpdc.2021.01.002
• Time-space trade-offs in population protocols for the majority problem
  
  Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2021). Time-space trade-offs in population protocols for the majority problem. Distributed Computing, 34(2), 91-111. https://doi.org/10.1007/s00446-020-00385-0
• Self-Stabilizing Balls and Bins in Batches
  
  Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2018). Self-Stabilizing Balls and Bins in Batches. Algorithmica, 80(12), 3673-3703. https://doi.org/10.1007/s00453-018-0411-z
• Threshold Load Balancing With Weighted Tasks
  
  Berenbrink, P., Friedetzky, T., Mallmann-Trenn, F., Meshkinfamfard, S., & Wastell, C. (2018). Threshold Load Balancing With Weighted Tasks. Journal of Parallel and Distributed Computing, 113, 218-226. https://doi.org/10.1016/j.jpdc.2017.10.012
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
  
  Berenbrink, P., Elsässer, R., & Friedetzky, T. (2016). Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. Distributed Computing, 29(5), 317-339. https://doi.org/10.1007/s00446-016-0264-0
• Randomized diffusion for indivisible loads
  
  Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2015). Randomized diffusion for indivisible loads. Journal of Computer and System Sciences, 81(1), 159-185. https://doi.org/10.1016/j.jcss.2014.04.027
• Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time
  
  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. https://doi.org/10.1002/rsa.20504
• Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems
  
  Miranda, A., Effert, S., Kang, Y., Miller, E. L., Popov, I., Brinkmann, A., Friedetzky, T., & Cortes, T. (2014). Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems. Transactions on Storage, 10(3), Article 9. https://doi.org/10.1145/2632230
• Balls into non-uniform bins
  
  Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2014). Balls into non-uniform bins. Journal of Parallel and Distributed Computing, 74(2), 2065-2076. https://doi.org/10.1016/j.jpdc.2013.10.008
• Balls into bins with related random choices
  
  Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2012). Balls into bins with related random choices. Journal of Parallel and Distributed Computing, 72(2), 246-253. https://doi.org/10.1016/j.jpdc.2011.10.006
• Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
  
  Berenbrink, P., Friedetzky, T., Hajirasouliha, I., & Hu, Z. (2012). Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks. Algorithmica, 62(3-4), 767-786. https://doi.org/10.1007/s00453-010-9482-1
• Sublinear-time algorithms for tournament graphs
  
  Dantchev, S., Friedetzky, T., & Nagel, L. (2011). Sublinear-time algorithms for tournament graphs. Journal of Combinatorial Optimization, 22, 469–481. https://doi.org/10.1007/s10878-010-9325-7
• A New Analytical Method for Parallel, Diffusion-type Load Balancing
  
  Berenbrink, P., Friedetzky, T., & Hu, Z. (2009). A New Analytical Method for Parallel, Diffusion-type Load Balancing. Journal of Parallel and Distributed Computing, 69(1), 54-61. https://doi.org/10.1016/j.jpdc.2008.05.005
• On the Stability of Dynamic Diffusion Load Balancing.
  
  Berenbrink, P., Friedetzky, T., & Martin, R. (2008). On the Stability of Dynamic Diffusion Load Balancing. Algorithmica, 50(3), 329-350. https://doi.org/10.1007/s00453-007-9081-y
• On weighted balls-into-bins games
  
  Berenbrink, P., Friedetzky, T., Hu, Z., & Martin, R. (2008). On weighted balls-into-bins games. Theoretical Computer Science, 409(3). https://doi.org/10.1016/j.tcs.2008.09.023
• Distributed selfish load balancing
  
  Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P. W., Hu, Z., Hu, Z. H., Martin, R. A., & Martin, R. (2007). Distributed selfish load balancing. SIAM Journal on Computing, 37(4), 1163-1181. https://doi.org/10.1137/060660345
• The degree distribution of the generalized duplication model
  
  Bebek, G., Berenbrink, P., Cooper, C., Friedetzky, T., Nadeau, J., & Sahinalp, S. (2006). The degree distribution of the generalized duplication model. Theoretical Computer Science, 369(1-3). https://doi.org/10.1016/j.tcs.2006.08.045
• (QUASI) SPANNERS FOR MOBILE AD HOC NETWORKS
  
  Berenbrink, P., Friedetzky, T., MaŇuch, J., & Stacho, L. (2005). (QUASI) SPANNERS FOR MOBILE AD HOC NETWORKS. Journal of Interconnection Networks, 06(02). https://doi.org/10.1142/s0219265905001320
• IDENTIFYING UNIFORMLY MUTATED SEGMENTS WITHIN REPEATS
  
  Sahinalp, S. C., Eichler, E., Goldberg, P., Berenbrink, P., Friedetzky, T., & Ergun, F. (2004). IDENTIFYING UNIFORMLY MUTATED SEGMENTS WITHIN REPEATS. Journal of Bioinformatics and Computational Biology, 02(04). https://doi.org/10.1142/s0219720004000788
• The natural work-stealing algorithm is stable
  
  Berenbrink, P., Friedetzky, T., & Goldberg, L. (2003). The natural work-stealing algorithm is stable. SIAM Journal on Computing, 32(5), 1260-1279. https://doi.org/10.1137/s0097539701399551