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., 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., 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
• Ṣ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, January). Payment scheduling in the Interval Debt Model. Presented at 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Novy Smokovec, Slovakia
• Berenbrink, P., Friedetzky, T., Hahn, C., Hintze, L., Kaaser, D., Kling, P., & Nagel, L. (2021, July). Infinite Balanced Allocation via Finite Capacities. Presented at 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), Washington, DC / Virtual
• Berenbrink, P., Friedetzky, T., Kaaser, D., & Kling, P. (2019, December). Tight & Simple Load Balancing. Presented at IEEE International Parallel & Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil
• Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2018, October). A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. Presented at International Symposium on DIStributed Computing (DISC), New Orleans, USA
• Elsässer, R., Friedetzky, T., Kaaser, D., & Mallmann-Trenn, F. (2017, July). Brief Announcement: Rapid Asynchronous Plurality Consensus. Presented at ACM Symposium on Principles of Distributed Computing (PODC), Washington D.C., USA
• Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., & Wastell, C. (2016, August). Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. Presented at 24th Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark
• Berenbrink, P., Friedetzky, T., Giakkoupis, G., & Kling, P. (2016, August). Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. Presented at 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy
• Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2016, December). Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins. Presented at ACM Symposium on Principles of Distributed Computing - PODC '16, Chicago, Illinois, USA
• Berenbrink, P., Brinkmann, A., Elsässer, R., Friedetzky, T., & Nagel, L. (2015, May). Randomized Renaming in Shared Memory Systems. Presented at 2015 IEEE 29th International Parallel and Distributed Processing Symposium., Hyderabad, India
• Berenbrink, P., Friedetzky, T., Mallmann-Trenn, F., Meshkinfamfard, S., & Wastell, C. (2015, May). Threshold Load Balancing with Weighted Tasks. Presented at 2015 IEEE 2015 IEEE 29th International Parallel and Distributed Processing Symposium., Hyderabad, India
• Berenbrink, P., Brinkmann, A., Friedetzky, T., Meister, D., & Nagel, L. (2013, December). Distributing Storage in Cloud Environments. Presented at 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum
• Berenbrink, P., Cooper, C., & Friedetzky, T. (2012, December). Random walks which prefer unvisited edges: exploring high girth even degree expanders in linear time. Presented at ACM Symposium on Principles of Distributed Computing - PODC '12, Madeira, Portugal
• Brinkmann, A., Popov, I., & Friedetzky, T. (2012, December). On the Influence of PRNGs on Data Distribution. Presented at 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing, Munich, Germany
• Berenbrink, P., Czumaj, A., Englert, M., Friedetzky, T., & Nagel, L. (2012, December). Multiple-Choice Balanced Allocation in (Almost) Parallel. Presented at APPROX/RANDOM 2012, Boston, USA
• Friedetzky, T., Gąsieniec, L., Gorry, T., & Martin, R. (2012, December). Observe and Remain Silent (Communication-Less Agent Location Discovery). Presented at Mathematical Foundations of Computer Science 2012, Bratislava, Slovakia
• Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2011, January). Randomized Diffusion for Indivisible Loads. Presented at Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms., San Francisco
• Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010, December). Balls into bins with related random choices. Presented at Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures - SPAA '10
• Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2010, December). Balls into non-uniform bins. Presented at 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)
• Dantchev, S., Friedetzky, T., & Nagel, L. (2009, July). Sublinear-Time Algorithms for Tournament Graphs. Presented at 15th Annual International Conference of Computing and Combinatorics (COCOON 2009), Niagara Falls, New York, USA
• Berenbrink, P., Elsaesser, R., & Friedetzky, T. (2008, December). 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
• Berenbrink, P., Friedetzky, T., & Hu, Z. (2006, December). A new analytical method for parallel, diffusion-type load balancing. Presented at Proceedings 20th IEEE International Parallel & Distributed Processing Symposium
• Berenbrink, P., Friedetzky, T., & Martin, R. (2005, July). Dynamic diffusion load balancing. Presented at 32nd International Colloquium on Automata, Languages and Programming : ICALP 2005, Lisboa, Portugal
• Adler, M., Berenbrink, P., Friedetzky, T., Goldberg, L. A., Goldberg, P., & Paterson, M. (2003, December). 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
• Berenbrink, P., Friedetzky, T., & Goldberg, L. (2001, December). The natural work-stealing algorithm is stable. Presented at Proceedings 2001 IEEE International Conference on Foundations of Computer Science
• Berenbrink, P., Czumaj, A., Friedetzky, T., & Vvedenskaya, N. D. (2000, December). Infinite parallel job allocation (extended abstract). Presented at Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures - SPAA '00
• Berenbrink, P., Friedetzky, T., & Steger, A. (1999, December). Randomized and adversarial load balancing. Presented at Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures - SPAA '99
• Berenbrink, P., Friedetzky, T., & Mayr, E. W. (1998, December). Parallel continuous randomized load balancing (extended abstract). Presented at Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA '98

Journal Article

• Dantchev, S., Friedetzky, T., & Nagel, L. (online). Sublinear-time algorithms for tournament graphs. Journal of Combinatorial Optimization, https://doi.org/10.1007/s10878-010-9325-7
• Stewart, I., Kutner, D., Friedetzky, T., Trehan, A., & Mertzios, G. (in press). Payment Scheduling in the Interval Debt Model. Theoretical Computer Science,
• 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., 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., 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., 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
• 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., 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
• 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., 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., 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
• 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