Staff profile

Personal webpage

• Distributed algorithms
• Probabilistic methods and algorithms

Chapter in book

• 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 (72-83). https://doi.org/10.1007/978-3-642-22993-0_10
• 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
• 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
• 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
• Berenbrink, P., Ergun, F., & Friedetzky, T. (2005). Finding Frequent Patterns in a String in Sublinear Time. In Algorithms – ESA 2005. https://doi.org/10.1007/11561071_66
• Berenbrink, P., Friedetzky, T., & Martin, R. (2005). Dynamic Diffusion Load Balancing. In Automata, Languages and Programming. https://doi.org/10.1007/11523468_112
• Ṣ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

• Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. . https://doi.org/10.1007/978-3-031-23101-8_18
• Berenbrink, P., Friedetzky, T., Hahn, C., Hintze, L., Kaaser, D., Kling, P., & Nagel, L. (2021). Infinite Balanced Allocation via Finite Capacities. . https://doi.org/10.1109/icdcs51616.2021.00096
• Berenbrink, P., Friedetzky, T., Kaaser, D., & Kling, P. (2019). Tight & Simple Load Balancing. In 33rd IEEE International Parallel & Distributed Processing Symposium ; proceedings (718-726). https://doi.org/10.1109/ipdps.2019.00080
• 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) (10:1-10:18). https://doi.org/10.4230/lipics.disc.2018.10
• 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 (363-365). https://doi.org/10.1145/3087801.3087860
• 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) (1-18). https://doi.org/10.4230/lipics.esa.2016.10
• 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) (1-14). https://doi.org/10.4230/lipics.icalp.2016.136
• 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 (83-92). https://doi.org/10.1145/2933057.2933092
• 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 (550-558). https://doi.org/10.1109/ipdps.2015.73
• 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 (542-549). https://doi.org/10.1109/ipdps.2015.77
• Berenbrink, P., Brinkmann, A., Friedetzky, T., Meister, D., & Nagel, L. (2013). Distributing Storage in Cloud Environments. . https://doi.org/10.1109/ipdpsw.2013.148
• 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. https://doi.org/10.1007/978-3-642-32512-0_35
• 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 (536-543). https://doi.org/10.1109/pdp.2012.58
• 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 (407-418). https://doi.org/10.1007/978-3-642-32589-2_37
• 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 (29-36). https://doi.org/10.1145/2332432.2332438
• 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 (429-439)
• Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010). Balls into bins with related random choices. . https://doi.org/10.1145/1810479.1810500
• Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010). Balls into non-uniform bins. . https://doi.org/10.1109/ipdps.2010.5470355
• 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 (459-471). https://doi.org/10.1007/978-3-642-02882-3_46
• Berenbrink, P., Elsaesser, R., & Friedetzky, T. (2008). Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. . https://doi.org/10.1145/1400751.1400773
• Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P. W., Hu, Z. H., & Martin, R. A. (2006). Distributed selfish load balancing. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (354--363)
• Berenbrink, P., Friedetzky, T., & Hu, Z. (2006). A new analytical method for parallel, diffusion-type load balancing. . https://doi.org/10.1109/ipdps.2006.1639292
• Adler, M., Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P., & Paterson, M. (2003). A proportionate fair scheduling rule with good worst-case performance. . https://doi.org/10.1145/777412.777430
• Berenbrink, P., Friedetzky, T., & Goldberg, L. (2001). The natural work-stealing algorithm is stable. . https://doi.org/10.1109/sfcs.2001.959892
• Berenbrink, P., Czumaj, A., Friedetzky, T., & Vvedenskaya, N. D. (2000). Infinite parallel job allocation (extended abstract). . https://doi.org/10.1145/341800.341813
• Berenbrink, P., Friedetzky, T., & Steger, A. (1999). Randomized and adversarial load balancing. . https://doi.org/10.1145/305619.305638
• Berenbrink, P., Friedetzky, T., & Mayr, E. W. (1998). Parallel continuous randomized load balancing (extended abstract). . https://doi.org/10.1145/277651.277685

Journal Article

• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Miranda, A., Effert, S., Kang, Y., Miller, E. L., Popov, I., Brinkmann, A., …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
• 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
• 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
• 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
• Dantchev, S., Friedetzky, T., & Nagel, L. (2010). Sublinear-time algorithms for tournament graphs. Journal of Combinatorial Optimization, https://doi.org/10.1007/s10878-010-9325-7
• 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
• 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
• 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
• Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P. W., Hu, Z., & Martin, R. (2007). Distributed Selfish Load Balancing. SIAM Journal on Computing, 37(4), https://doi.org/10.1137/060660345
• 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
• 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
• 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
• 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