Skip to main content

Research Repository

Advanced Search

Outputs (54)

Payment scheduling in the Interval Debt Model (2023)
Conference Proceeding
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

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.

Infinite Balanced Allocation via Finite Capacities (2021)
Conference Proceeding
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

We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are n bins (servers) with a limited capacity (buffer) of size c=c(n)∈N . Given a fixed arrival rate λ=λ(n)∈(0,1) , in every round λn new ball... Read More about Infinite Balanced Allocation via Finite Capacities.

Randomized renaming in shared memory systems (2021)
Journal Article
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

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were develo... Read More about Randomized renaming in shared memory systems.

Time-space trade-offs in population protocols for the majority problem (2020)
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

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion w... Read More about Time-space trade-offs in population protocols for the majority problem.

Tight & Simple Load Balancing (2019)
Conference Proceeding
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

We consider the following load balancing process for m tokens distributed arbitrarily among n nodes connected by a complete graph. In each time step a pair of nodes is selected uniformly at random. Let ℓ 1 and ℓ 2 be their respective number of tokens... Read More about Tight & Simple Load Balancing.

A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states (2018)
Conference Proceeding
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

A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired outpu... Read More about A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states.

Self-Stabilizing Balls and Bins in Batches (2018)
Journal Article
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

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where m balls (tasks) are to be d... Read More about Self-Stabilizing Balls and Bins in Batches.

Threshold Load Balancing With Weighted Tasks (2017)
Journal Article
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

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m≥n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a thres... Read More about Threshold Load Balancing With Weighted Tasks.

Brief Announcement: Rapid Asynchronous Plurality Consensus (2017)
Conference Proceeding
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

We consider distributed plurality consensus on a complete graph of size n with k initial opinions in the following asynchronous communication model. Each node is equipped with a random Poisson clock with parameter lambda=1. Whenever a node's clock ti... Read More about Brief Announcement: Rapid Asynchronous Plurality Consensus.

Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing (2016)
Conference Proceeding
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

We consider plurality consensus in networks of n nodes. Initially, each node has one of k opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). In certai... Read More about Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing.

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time (2016)
Conference Proceeding
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

Plurality consensus considers a network of n nodes, each having one of k opinions. Nodes execute a (randomized) distributed protocol with the goal that all nodes adopt the plurality (the opinion initially supported by the most nodes). Communication i... Read More about Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time.

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems (2016)
Journal Article
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

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly c... Read More about Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems.

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins (2016)
Conference Proceeding
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

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be... Read More about Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins.

Threshold Load Balancing with Weighted Tasks (2015)
Conference Proceeding
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

We study threshold-based load balancing protocols for weighted tasks. We are given an arbitrary graph G with n nodes (resources, bins) and m > n tasks (balls). Initially the tasks are distributed arbitrarily over the n nodes. The resources have a thr... Read More about Threshold Load Balancing with Weighted Tasks.

Randomized Renaming in Shared Memory Systems (2015)
Conference Proceeding
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

Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were develo... Read More about Randomized Renaming in Shared Memory Systems.

Randomized diffusion for indivisible loads (2015)
Journal Article
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

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tok... Read More about Randomized diffusion for indivisible loads.

Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems (2014)
Journal Article
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

The ever-growing amount of data requires highly scalable storage solutions. The most flexible approach is to use storage pools that can be expanded and scaled down by adding or removing storage devices. To make this approach usable, it is necessary t... Read More about Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems.

Balls into non-uniform bins (2014)
Journal Article
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 games for uniform bins are widely used to model randomised load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. The... Read More about Balls into non-uniform bins.

Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time (2013)
Journal Article
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

Let G = (V,E) be a connected graph with |V | = n vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified... Read More about Random walks which prefer unvisited edges : exploring high girth even degree expanders in linear time.

Randomized Diffusion for Indivisible Loads (2011)
Conference Proceeding
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)

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tok... Read More about Randomized Diffusion for Indivisible Loads.

Sublinear-Time Algorithms for Tournament Graphs (2009)
Conference Proceeding
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

We show that a random walk on a tournament on n vertices finds either a sink or a 3-cycle in expected time O (√n ∙ log n ∙ √log*n), that is, sublinear both in the size of the description of the graph as well as in the number of vertices. This result... Read More about Sublinear-Time Algorithms for Tournament Graphs.

Distributed selfish load balancing (2006)
Conference Proceeding
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)

The natural work-stealing algorithm is stable (2003)
Journal Article
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

In this paper we analyze a very simple dynamic work-stealing algorithm. In the work-generation model, there are n (work) generators. A generator-allocation function is simply a function from the n generators to the n processors. We consider a fixed,... Read More about The natural work-stealing algorithm is stable.