Skip to main content

Research Repository

Advanced Search

All Outputs (27)

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.

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.

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.

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 (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.