28 Search Results for "Schmid, Stefan"

Document
DOI: 10.4230/LIPIcs.STACS.2024.14
A Subquadratic Bound for Online Bisection

Authors: Marcin Bienkowski and Stefan Schmid

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The online bisection problem is a natural dynamic variant of the classic optimization problem, where one has to dynamically maintain a partition of n elements into two clusters of cardinality n/2. During runtime, an online algorithm is given a sequence of requests, each being a pair of elements: an inter-cluster request costs one unit while an intra-cluster one is free. The algorithm may change the partition, paying a unit cost for each element that changes its cluster. This natural problem admits a simple deterministic O(n²)-competitive algorithm [Avin et al., DISC 2016]. While several significant improvements over this result have been obtained since the original work, all of them either limit the generality of the input or assume some form of resource augmentation (e.g., larger clusters). Moreover, the algorithm of Avin et al. achieves the best known competitive ratio even if randomization is allowed. In this paper, we present the first randomized online algorithm that breaks this natural quadratic barrier and achieves a competitive ratio of Õ(n^{23/12}) without resource augmentation and for an arbitrary sequence of requests.
Cite as

Marcin Bienkowski and Stefan Schmid. A Subquadratic Bound for Online Bisection. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.STACS.2024.14,
  author =	{Bienkowski, Marcin and Schmid, Stefan},
  title =	{{A Subquadratic Bound for Online Bisection}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.14},
  URN =		{urn:nbn:de:0030-drops-197247},
  doi =		{10.4230/LIPIcs.STACS.2024.14},
  annote =	{Keywords: Bisection, Graph Partitioning, online balanced Repartitioning, online Algorithms, competitive Analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.11
On the Convergence Time in Graphical Games: A Locality-Sensitive Approach

Authors: Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of "time-constrained" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.
Cite as

Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. On the Convergence Time in Graphical Games: A Locality-Sensitive Approach. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirvonen_et_al:LIPIcs.OPODIS.2023.11,
  author =	{Hirvonen, Juho and Schmid, Laura and Chatterjee, Krishnendu and Schmid, Stefan},
  title =	{{On the Convergence Time in Graphical Games: A Locality-Sensitive Approach}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{11:1--11:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.11},
  URN =		{urn:nbn:de:0030-drops-195015},
  doi =		{10.4230/LIPIcs.OPODIS.2023.11},
  annote =	{Keywords: distributed computing, Nash equilibria, mechanism design, best-response dynamics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.44
Online Algorithms with Randomly Infused Advice

Authors: Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
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 contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer ℬ from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 ≤ α ≤ 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - α, then the buffer ℬ contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter α increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems.
Cite as

Yuval Emek, Yuval Gil, Maciej Pacut, and Stefan Schmid. Online Algorithms with Randomly Infused Advice. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ESA.2023.44,
  author =	{Emek, Yuval and Gil, Yuval and Pacut, Maciej and Schmid, Stefan},
  title =	{{Online Algorithms with Randomly Infused Advice}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.44},
  URN =		{urn:nbn:de:0030-drops-186970},
  doi =		{10.4230/LIPIcs.ESA.2023.44},
  annote =	{Keywords: Online algorithms, competitive analysis, advice}
}
Document
DOI: 10.4230/DagRep.12.11.96
Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471)

Authors: Artur Hecker, Stefan Schmid, Henning Schulzrinne, Lily Hügerich, Sándor Laki, and Iosif Salem

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22471 "Towards More Flexible and Automated Communication Networks". Communication network are becoming more and more automated, allowing to overcome human configuration errors (a frequent reason for outages) and enabling a more fine-grained control, potentially improving also efficiency. For example, the percentage of employees of Telecom companies "really touching the network" is decreasing. The goal of this seminar was to bring together experts in the field to identify and discuss the key challenges in making communication networks more autonomous. To this end, the seminar was structured around a small number of enlightning keynote talks, leaving significant time for breakout sessions and discussions, as well as socializing.
Cite as

Artur Hecker, Stefan Schmid, Henning Schulzrinne, Lily Hügerich, Sándor Laki, and Iosif Salem. Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471). In Dagstuhl Reports, Volume 12, Issue 11, pp. 96-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{hecker_et_al:DagRep.12.11.96,
  author =	{Hecker, Artur and Schmid, Stefan and Schulzrinne, Henning and H\"{u}gerich, Lily and Laki, S\'{a}ndor and Salem, Iosif},
  title =	{{Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471)}},
  pages =	{96--108},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Hecker, Artur and Schmid, Stefan and Schulzrinne, Henning and H\"{u}gerich, Lily and Laki, S\'{a}ndor and Salem, Iosif},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.11.96},
  URN =		{urn:nbn:de:0030-drops-178379},
  doi =		{10.4230/DagRep.12.11.96},
  annote =	{Keywords: networking, communication technologies, automation, programmability, flexibility}
}
Document
DOI: 10.4230/OASIcs.EVCS.2023.5
Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics

Authors: Houda Boukham, Guido Wachsmuth, Toine Hartman, Hamza Boucherit, Oskar van Rest, Hassan Chafi, Sungpack Hong, Martijn Dwars, Arnaud Delamare, and Dalila Chiadmi

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
For the last decade, teams at Oracle relied on the Spoofax language workbench to develop a family of domain-specific languages for graph analytics in research projects and in product development. In this paper, we analyze the requirements for integrating language processors into large-scale graph analytics toolkits and for the development of these language processors as part of a larger product development process. We discuss how Spoofax helps to meet these requirements and point out the need for future improvements.
Cite as

Houda Boukham, Guido Wachsmuth, Toine Hartman, Hamza Boucherit, Oskar van Rest, Hassan Chafi, Sungpack Hong, Martijn Dwars, Arnaud Delamare, and Dalila Chiadmi. Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 5:1-5:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boukham_et_al:OASIcs.EVCS.2023.5,
  author =	{Boukham, Houda and Wachsmuth, Guido and Hartman, Toine and Boucherit, Hamza and van Rest, Oskar and Chafi, Hassan and Hong, Sungpack and Dwars, Martijn and Delamare, Arnaud and Chiadmi, Dalila},
  title =	{{Spoofax at Oracle: Domain-Specific Language Engineering for Large-Scale Graph Analytics}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{5:1--5:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-177756},
  doi =		{10.4230/OASIcs.EVCS.2023.5},
  annote =	{Keywords: language workbench, domain-specific language}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.36
Dynamic Maintenance of Monotone Dynamic Programs and Applications

Authors: Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
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, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1+ε)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0,W] using only polylog(n,W) bits, and to perform operations, such as (min,+)-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.
Cite as

Monika Henzinger, Stefan Neumann, Harald Räcke, and Stefan Schmid. Dynamic Maintenance of Monotone Dynamic Programs and Applications. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.STACS.2023.36,
  author =	{Henzinger, Monika and Neumann, Stefan and R\"{a}cke, Harald and Schmid, Stefan},
  title =	{{Dynamic Maintenance of Monotone Dynamic Programs and Applications}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.36},
  URN =		{urn:nbn:de:0030-drops-176889},
  doi =		{10.4230/LIPIcs.STACS.2023.36},
  annote =	{Keywords: Dynamic programming, dynamic algorithms, data structures}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.25
Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks

Authors: Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Emerging reconfigurable datacenter networks (RDCNs) are a particularly innovative approach to improve datacenter throughput. Relying on a dynamic optical topology which can be adjusted towards the workload in a demand-aware manner, RDCNs allow to exploit temporal and spatial locality in the communication pattern, and to provide topological shortcuts for frequently communicating racks. The key challenge, however, concerns how to realize demand-awareness in RDCNs in a scalable fashion. This paper presents and evaluates Chopin, a hybrid scheduler for self-adjusting networks that provides demand-awareness at low overhead, by combining centralized and distributed approaches. Chopin allocates optical circuits to elephant flows, through its slower centralized scheduler, utilizing global information. Chopin’s distributed scheduler is orders of magnitude faster and can swiftly react to changes in the traffic and adjust the optical circuits accordingly, by using only local information and running at each rack separately.
Cite as

Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay. Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rozenschiff_et_al:LIPIcs.OPODIS.2022.25,
  author =	{Rozen-Schiff, Neta and Foerster, Klaus-Tycho and Schmid, Stefan and Hay, David},
  title =	{{Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.25},
  URN =		{urn:nbn:de:0030-drops-176457},
  doi =		{10.4230/LIPIcs.OPODIS.2022.25},
  annote =	{Keywords: reconfigurable optical networks, centralized scheduler, distributed scheduler}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.47
Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks

Authors: Antoine El-Hayek, Monika Henzinger, and Stefan Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n. We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem. Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem. For the two latter problems no upper or lower bounds were previously known.
Cite as

Antoine El-Hayek, Monika Henzinger, and Stefan Schmid. Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 47:1-47:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{elhayek_et_al:LIPIcs.ITCS.2023.47,
  author =	{El-Hayek, Antoine and Henzinger, Monika and Schmid, Stefan},
  title =	{{Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{47:1--47:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.47},
  URN =		{urn:nbn:de:0030-drops-175502},
  doi =		{10.4230/LIPIcs.ITCS.2023.47},
  annote =	{Keywords: broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.100
The Time Complexity of Consensus Under Oblivious Message Adversaries

Authors: Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs 𝐃 arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set 𝐃, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.
Cite as

Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid. The Time Complexity of Consensus Under Oblivious Message Adversaries. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 100:1-100:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{winkler_et_al:LIPIcs.ITCS.2023.100,
  author =	{Winkler, Kyrill and Paz, Ami and Rincon Galeana, Hugo and Schmid, Stefan and Schmid, Ulrich},
  title =	{{The Time Complexity of Consensus Under Oblivious Message Adversaries}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{100:1--100:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.100},
  URN =		{urn:nbn:de:0030-drops-176030},
  doi =		{10.4230/LIPIcs.ITCS.2023.100},
  annote =	{Keywords: dynamic networks, oblivious message adversaries, consensus, time complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.42
Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies

Authors: Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities.
Cite as

Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.DISC.2022.42,
  author =	{Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan},
  title =	{{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.42},
  URN =		{urn:nbn:de:0030-drops-172330},
  doi =		{10.4230/LIPIcs.DISC.2022.42},
  annote =	{Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.52
Brief Announcement: Temporal Locality in Online Algorithms

Authors: Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms.
Cite as

Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko. Brief Announcement: Temporal Locality in Online Algorithms. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pacut_et_al:LIPIcs.DISC.2022.52,
  author =	{Pacut, Maciej and Parham, Mahmoud and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka and Tereshchenko, Aleksandr},
  title =	{{Brief Announcement: Temporal Locality in Online Algorithms}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{52:1--52:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.52},
  URN =		{urn:nbn:de:0030-drops-172431},
  doi =		{10.4230/LIPIcs.DISC.2022.52},
  annote =	{Keywords: Online algorithms, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.9
Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion

Authors: Gregor Bankhamer, Robert Elsässer, and Stefan Schmid

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
To ensure high availability, datacenter networks must rely on local fast rerouting mechanisms that allow routers to quickly react to link failures, in a fully decentralized manner. However, configuring these mechanisms to provide a high resilience against multiple failures while avoiding congestion along failover routes is algorithmically challenging, as the rerouting rules can only depend on local failure information and must be defined ahead of time. This paper presents a randomized local fast rerouting algorithm for Clos networks, the predominant datacenter topologies. Given a graph G = (V,E) describing a Clos topology, our algorithm defines local routing rules for each node v ∈ V, which only depend on the packet’s destination and are conditioned on the incident link failures. We prove that as long as number of failures at each node does not exceed a certain bound, our algorithm achieves an asymptotically minimal congestion up to polyloglog factors along failover paths. Our lower bounds are developed under some natural routing assumptions.
Cite as

Gregor Bankhamer, Robert Elsässer, and Stefan Schmid. Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bankhamer_et_al:LIPIcs.DISC.2021.9,
  author =	{Bankhamer, Gregor and Els\"{a}sser, Robert and Schmid, Stefan},
  title =	{{Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.9},
  URN =		{urn:nbn:de:0030-drops-148117},
  doi =		{10.4230/LIPIcs.DISC.2021.9},
  annote =	{Keywords: local failover routing, congestion, randomized algorithms, datacenter networks}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.58
Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model

Authors: Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).
Cite as

Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 58:1-58:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{korhonen_et_al:LIPIcs.DISC.2021.58,
  author =	{Korhonen, Janne H. and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka},
  title =	{{Brief Announcement: Sinkless Orientation Is Hard Also in the Supported LOCAL Model}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{58:1--58:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.58},
  URN =		{urn:nbn:de:0030-drops-148609},
  doi =		{10.4230/LIPIcs.DISC.2021.58},
  annote =	{Keywords: Supported LOCAL model, sinkless orientation, round elimination}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.26
Maximally Resilient Replacement Paths for a Family of Product Graphs

Authors: Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall). This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.
Cite as

Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid. Maximally Resilient Replacement Paths for a Family of Product Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{parham_et_al:LIPIcs.OPODIS.2020.26,
  author =	{Parham, Mahmoud and Foerster, Klaus-Tycho and Kosic, Petar and Schmid, Stefan},
  title =	{{Maximally Resilient Replacement Paths for a Family of Product Graphs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.26},
  URN =		{urn:nbn:de:0030-drops-135111},
  doi =		{10.4230/LIPIcs.OPODIS.2020.26},
  annote =	{Keywords: Product Graphs, Resilience, Failures, Routing}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.46
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

Authors: Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.
Cite as

Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.DISC.2020.46,
  author =	{Foerster, Klaus-Tycho and Hirvonen, Juho and Pignolet, Yvonne-Anne and Schmid, Stefan and Tredan, Gilles},
  title =	{{Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{46:1--46:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.46},
  URN =		{urn:nbn:de:0030-drops-131244},
  doi =		{10.4230/LIPIcs.DISC.2020.46},
  annote =	{Keywords: Resilience, Local Failover}
}
  • Refine by Author
  • 27 Schmid, Stefan
  • 5 Foerster, Klaus-Tycho
  • 3 Avin, Chen
  • 3 Parham, Mahmoud
  • 2 Chatterjee, Krishnendu
  • Show More...

  • Refine by Classification
  • 5 Networks → Network algorithms
  • 4 Networks → Routing protocols
  • 4 Theory of computation → Distributed algorithms
  • 3 Theory of computation → Online algorithms
  • 2 Computer systems organization → Dependable and fault-tolerant systems and networks
  • Show More...

  • Refine by Keyword
  • 2 Churn
  • 2 Online algorithms
  • 2 P2P Topologies
  • 2 Reconfigurable Networks
  • 2 Resilience
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 7 2023
  • 3 2017
  • 3 2019
  • 3 2021
  • 2 2006
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact