128 citations · 139 across the 20 of their papers we have counts for
26 papers
Demand-Aware Network Design with Steiner Nodes and a Connection to Virtual Network Embedding
Aleksander Figiel, Janne H. Korhonen, Neil Olver +1
Emerging optical and virtualization technologies enable the design of more flexible and demand-aware networked systems, in which resources can be optimized toward the actual worklo…
RIFO: Pushing the Efficiency of Programmable Packet Schedulers
Habib Mostafaei, Maciej Pacut, Stefan Schmid
Packet scheduling is a fundamental networking task that recently received renewed attention in the context of programmable data planes. Programmable packet scheduling systems such…
Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults
Christoph Lenzen, Moti Medina, Mehrdad Saberi +1
With the increasing scale of communication networks, the likelihood of failures grows as well. Since these networks form a critical backbone of our digital society, it is important…
MCQUIC - A Multicast Extension for QUIC
Max Franke, Jake Holland, Stefan Schmid
Mass live content, such as world cups, the Superbowl or the Olympics, attract audiences of hundreds of millions of viewers. While such events were predominantly consumed on TV, mor…
Dynamic Probabilistic Reliable Broadcast
Veronika Anikina, João Paulo Bezerra, Petr Kuznetsov +2
Byzantine reliable broadcast is a fundamental primitive in distributed systems that allows a set of processes to agree on a message broadcast by a dedicated process, even when some…
An Improved Subquadratic Bound for Online Bisection
Marcin Bienkowski, Stefan Schmid
The online bisection problem is a natural dynamic variant of the classic bisection problem, where one has to dynamically maintain a partition of elements into two clusters of c…
Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
Harald Räcke, Stefan Schmid, Ruslan Zabrodin
The performance of many large-scale and data-intensive distributed systems critically depends on the capacity of the interconnecting network. This paper is motivated by the vision…
Topological Characterization of Consensus Solvability in Directed Dynamic Networks
Hugo Rincon Galeana, Ulrich Schmid, Kyrill Winkler +2
Consensus is one of the most fundamental problems in distributed computing. This paper studies the consensus problem in a synchronous dynamic directed network, in which communicati…
Performance Analysis of Machine Learning Centered Workload Prediction Models for Cloud
Deepika Saxena, Jitendra Kumar, Ashutosh Kumar Singh +1
The precise estimation of resource usage is a complex and challenging issue due to the high variability and dimensionality of heterogeneous service types and dynamic workloads. Ove…
Toward Self-Adjusting k-ary Search Tree Networks
Evgenii Feder, Anton Paramonov, Pavel Mavrin +3
Datacenter networks are becoming increasingly flexible with the incorporation of new networking technologies, such as optical circuit switches. These technologies allow for program…
Time Complexity of Broadcast and Consensus for Randomized Oblivious Message Adversaries
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Broadcast and consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network lin…
Online Algorithms with Randomly Infused Advice
Yuval Emek, Yuval Gil, Maciej Pacut +1
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In cont…
SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree
Arash Pourdamghani, Chen Avin, Robert Sama +1
We consider the fundamental problem of designing a self-adjusting tree, which efficiently and locally adapts itself towards the demand it serves (namely accesses to the items store…
Dynamic Maintenance of Monotone Dynamic Programs and Applications
Monika Henzinger, Stefan Neumann, Harald Räcke +1
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays…
Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters
Kathrin Hanauer, Monika Henzinger, Lara Ost +1
Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured…
Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks
Neta Rozen Schiff, Klaus-Tycho Foerster, Stefan Schmid +1
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Emerging reconfigurable datacenter networks (RDCNs) are a part…
The Augmentation-Speed Tradeoff for Consistent Network Updates
Monika Henzinger, Ami Paz, Arash Pourdamghani +1
Emerging software-defined networking technologies enable more adaptive communication infrastructures, allowing for quick reactions to changes in networking requirements by exploiti…
Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
We study the broadcast problem on dynamic networks with processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is give…
Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting …
Online Admission Control and Rebalancing in Payment Channel Networks
Mahsa Bastankhah, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali +3
Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain rout…
Optimizing Reconfigurable Optical Datacenters: The Power of Randomization
Marcin Bienkowski, David Fuchssteiner, Stefan Schmid
Reconfigurable optical topologies are a promising new technology to improve datacenter network performance and cope with the explosive growth of traffic. In particular, these netwo…
Model-Based Insights on the Performance, Fairness, and Stability of BBR
Simon Scherrer, Markus Legner, Adrian Perrig +1
Google's BBR is the most prominent result of the recently revived quest for efficient, fair, and flexible congestion-control algorithms (CCAs). While the performance of BBR has bee…
Self-Adjusting Linear Networks with Ladder Demand Graph
Anton Paramonov, Iosif Salem, Stefan Schmid +1
Self-adjusting networks (SANs) have the ability to adapt to communication demand by dynamically adjusting the workload (or demand) embedding, i.e., the mapping of communication req…
Sinkless Orientation Made Simple
Alkida Balliu, Janne H. Korhonen, Fabian Kuhn +9
The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distribut…