5 Search Results for "Godfrey, Philip Brighten"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.31
Fast Re-Routing in Networks: On the Complexity of Perfect Resilience

Authors: Matthias Bentert, Esra Ceylan, Valentin Hübner, Stefan Schmid, and Jiří Srba

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
To achieve fast recovery from link failures, most modern communication networks feature fully decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time).
Cite as

Matthias Bentert, Esra Ceylan, Valentin Hübner, Stefan Schmid, and Jiří Srba. Fast Re-Routing in Networks: On the Complexity of Perfect Resilience. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.OPODIS.2025.31,
  author =	{Bentert, Matthias and Ceylan, Esra and H\"{u}bner, Valentin and Schmid, Stefan and Srba, Ji\v{r}{\'\i}},
  title =	{{Fast Re-Routing in Networks: On the Complexity of Perfect Resilience}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.31},
  URN =		{urn:nbn:de:0030-drops-252040},
  doi =		{10.4230/LIPIcs.OPODIS.2025.31},
  annote =	{Keywords: routing in computer networks, fast re-route, perfect resilience, complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.43
New Approximate Distance Oracles and Their Applications

Authors: Avi Kadria and Liam Roditty

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let G = (V, E) be an undirected graph with n vertices and m edges, and let μ = m/n. A distance oracle is a data structure designed to answer approximate distance queries, with the goal of achieving low stretch, efficient space usage, and fast query time. While much of the prior work focused on distance oracles with constant query time, this paper presents a comprehensive study of distance oracles with non-constant query time. We explore the tradeoffs between space, stretch, and query time of distance oracles in various regimes. Specifically, we consider both weighted and unweighted graphs in the regimes of stretch < 2 and stretch ≥ 2. In addition, we demonstrate several applications of our new distance oracles to the n-Pairs Shortest Paths (n-PSP) problem and the All Nodes Shortest Cycles (ANSC) problem. Our main contributions are: - Weighted graphs: We present a new three-way trade-off between stretch, space, and query time, offering a natural extension of the classical Thorup–Zwick distance oracle [STOC’01 and JACM’05] to regimes with larger query time. Specifically, for any 0 < r < 1/2 and integer k ≥ 1, we construct a (2k(1 - 2r) - 1)-stretch distance oracle with Õ(m + n^{1 + 1/k}) space and Õ(μ n^r) query time. This construction provides an asymptotic improvement over the classical (2k - 1)-stretch and O(n^{1 + 1/k})-space tradeoff of Thorup and Zwick in sparse graphs, at the cost of increased query time. We also improve upon a result of Dalirrooyfard et al. [FOCS’22], who presented a (2k - 2)-stretch distance oracle with O(m + n^{1 + 1/k}) space and O(μ n^{1/k}) query time. In our oracle we reduce the stretch from (2k - 2) to (2k - 5) while preserving the same space and query time. - Unweighted graphs: We present a (2k - 5, 4 + 2_{odd})-approximation distance oracle with O(n^{1 + 1/k}) space and O(n^{1/k}) query time. This improves upon a (2k - 2, 2_{odd})-approximation distance oracle of Dalirrooyfard et al. [FOCS’22] while maintaining the same space and query time. We also present a distance oracle that given u,v ∈ V returns an estimate d̂(u,v) ≤ d(u,v) + 2⌈ d(u,v) / 3 ⌉ + 2, using O(n^{4/3 + 2ε}) space and O(n^{1 - 3ε}) query time. To the best of our knowledge, this is the first distance oracle that simultaneously achieves a multiplicative stretch < 2, and a space complexity O(n^{1.5 - α}), for some α > 0. - Applications for n-PSP and ANSC: We present an Õ(m^{1 - 1/(k+1)} n)-time algorithm for the n-PSP problem, that for every input pair ⟨s_i,t_i⟩, where i ∈ [n], returns an estimate d̂(s_i, t_i) such that d̂(s_i,t_i) ≤ d(s_i,t_i) + 2⌈d(s_i,t_i)/2k⌉. By allowing a small additive error, this result circumvents the conditional running time lower bound of Ω(m^{2 - 2/(k+1)} ⋅ n^{1/(k+1) - o(1)}), established by Dalirrooyfard et al. [FOCS’22] for achieving (1 + 1/k)-stretch. Additionally, we present an Õ(mn^{1 - 1/k})-time algorithm for the ANSC problem that computes, for every u ∈ V, an estimate ĉ_u such that ĉ_u ≤ SC(u) + 2⌈SC(u)/2(k - 1)⌉, where SC(u) denotes the length of the shortest cycle containing u. This improves upon the Õ(m^{2 - 2/k}n^{1/k})-time algorithm of Dalirrooyfard et al. [FOCS'22], while achieving the same approximation guarantee. We obtain our results by developing several new techniques, among them are the borderline vertices technique and the middle vertex technique, which may be of independent interest.
Cite as

Avi Kadria and Liam Roditty. New Approximate Distance Oracles and Their Applications. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kadria_et_al:LIPIcs.ISAAC.2025.43,
  author =	{Kadria, Avi and Roditty, Liam},
  title =	{{New Approximate Distance Oracles and Their Applications}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{43:1--43:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.43},
  URN =		{urn:nbn:de:0030-drops-249514},
  doi =		{10.4230/LIPIcs.ISAAC.2025.43},
  annote =	{Keywords: Distance oracles, Fine-grained algorithms, Graph algorithms, Data structures}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.1
Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics

Authors: Kinter Ren and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this paper we look at various extensions of the classic Traveling Salesman Problem (TSP) on graphs with bounded doubling dimension and bounded treewidth and present approximation schemes for them. Suppose we are given a weighted graph G = (V,E) with a start node s ∈ V, distances on the edges d:E → ℚ^+ and integer k. In k-stroll problem the goal is to find a path from s of minimum length that visits at least k vertices. In k-path we are given an additional end node t ∈ V and the path is supposed to go from s to t. The dual problem to k-stroll is the rooted orienteering in which instead of k we are given a budget B and the goal is to find a walk of length at most B starting at s that visits as many vertices as possible. In the point-to-point orienteering (P2P orienteering) we are given start and end nodes s,t and the walk is supposed to start at s and end at t. In the deadline TSP (which generalizes P2P orienteering) we are given a deadline D(v) for each v ∈ V and the goal is to find a walk starting at s that visits as many vertices as possible before their deadline (where the visit time of a node is the distance travelled from s to that node). The best approximation for rooted orienteering (or P2P orienteering) is (2+ε)-approximation [Chekuri et al., 2012] and O(log n)-approximation for deadline TSP [Nikhil Bansal et al., 2004]. For Euclidean metrics of fixed dimension, Chen and Har-Peled present [Chen and Har-Peled, 2008] a PTAS for rooted orienteering. There is no known approximation scheme for deadline TSP for any metric (not even trees). Our main result is the first approximation scheme for deadline TSP on metrics with bounded doubling dimension (which includes Euclidean metrics). To do so we first we present a quasi-polynomial time approximation scheme for k-path and P2P orienteering on such metrics. More specifically, if G is a metric with doubling dimension κ and aspect ratio Δ, we present a (1+ε)-approximation that runs in time n^{O((logΔ/ε) ^{2κ+1})}. Building upon these, we obtain an approximation scheme for deadline TSP when the distances and deadlines are integer which runs in time n^{O((log Δ/ε) ^{2κ+2})}. The same approach also implies a bicriteria (1+ε,1+ε)-approximation for deadline TSP for when distances and deadlines are in ℚ^+. For graphs with bounded treewidth ω we show how to solve k-path and P2P orienteering exactly in polynomial time and a (1+ε)-approximation for deadline TSP in time n^O((ωlogΔ/ε)²).
Cite as

Kinter Ren and Mohammad R. Salavatipour. Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.APPROX/RANDOM.2025.1,
  author =	{Ren, Kinter and Salavatipour, Mohammad R.},
  title =	{{Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.1},
  URN =		{urn:nbn:de:0030-drops-243678},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.1},
  annote =	{Keywords: Deadline Traveling Salesman Problem, Orienteering, Doubling Metrics, Approximation algorithm}
}
Document
DOI: 10.4230/LITES-v004-i001-a005
Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains

Authors: Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram

Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1

Abstract
As data centers attempt to cope with the exponential growth of data, new techniques for intelligent, software-defined data centers (SDDC) are being developed to confront the scale and pace of changing resources and requirements.  For cost-constrained environments, like those increasingly present in scientific research labs, SDDCs also may provide better reliability and performability with no additional hardware through the use of dynamic syndrome allocation. To do so, the middleware layers of SDDCs must be able to calculate and account for complex dependence relationships to determine an optimal data layout.  This challenge is exacerbated by the growth of constraints on the dependence problem when available resources are both large (due to a higher number of syndromes that can be stored) and small (due to the lack of available space for syndrome allocation). We present a quantitative method for characterizing these challenges using an analysis of attack domains for high-dimension variants of the $n$-queens problem that enables performable solutions via the SMT solver Z3. We demonstrate correctness of our technique, and provide experimental evidence of its efficacy; our implementation is publicly available.
Cite as

Eric W. D. Rozier, Kristin Y. Rozier, and Ulya Bayram. Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 05:1-05:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{rozier_et_al:LITES-v004-i001-a005,
  author =	{Rozier, Eric W. D. and Rozier, Kristin Y. and Bayram, Ulya},
  title =	{{Characterizing Data Dependence Constraints for Dynamic Reliability Using n-Queens Attack Domains}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{05:1--05:26},
  ISSN =	{2199-2002},
  year =	{2017},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a005},
  URN =		{urn:nbn:de:0030-drops-192667},
  doi =		{10.4230/LITES-v004-i001-a005},
  annote =	{Keywords: SMT, Data dependence, n-queens}
}
Document
DOI: 10.4230/DagRep.5.2.44
Formal Foundations for Networking (Dagstuhl Seminar 15071)

Authors: Nikolaj Bjorner, Nate Foster, Philip Brighten Godfrey, and Pamela Zave

Published in: Dagstuhl Reports, Volume 5, Issue 2 (2015)

Abstract
This report documents the program and outcomes of Dagstuhl Seminar 15071 "Formal Foundations for Networking." Networking is in the midst of a revolution being driven by rapidly expanding infrastructures and emerging software-defined networking architectures. There is a growing need for tools and methodologies that provide rigorous guarantees about performance, reliability, and security. This seminar brought together leading researchers and practitioners from the fields of formal methods, networking, programming languages, and security, to investigate the task of developing formal foundations for networks.
Cite as

Nikolaj Bjorner, Nate Foster, Philip Brighten Godfrey, and Pamela Zave. Formal Foundations for Networking (Dagstuhl Seminar 15071). In Dagstuhl Reports, Volume 5, Issue 2, pp. 44-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{bjorner_et_al:DagRep.5.2.44,
  author =	{Bjorner, Nikolaj and Foster, Nate and Godfrey, Philip Brighten and Zave, Pamela},
  title =	{{Formal Foundations for Networking (Dagstuhl Seminar 15071)}},
  pages =	{44--63},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{2},
  editor =	{Bjorner, Nikolaj and Foster, Nate and Godfrey, Philip Brighten and Zave, Pamela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.2.44},
  URN =		{urn:nbn:de:0030-drops-50440},
  doi =		{10.4230/DagRep.5.2.44},
  annote =	{Keywords: Formal methods, logic, middleboxes, model checking, networking, program synthesis, security, software-defined networking, verification}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2017
  • 1 2015

  • Refine by Author
  • 1 Bayram, Ulya
  • 1 Bentert, Matthias
  • 1 Bjorner, Nikolaj
  • 1 Ceylan, Esra
  • 1 Foster, Nate
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 LITES
  • 1 DagRep

  • Refine by Classification
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Hardware → Theorem proving and SAT solving
  • 1 Information systems → Data centers
  • 1 Mathematics of computing → Graph algorithms
  • 1 Networks → Network properties
  • Show More...

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Data dependence
  • 1 Data structures
  • 1 Deadline Traveling Salesman Problem
  • 1 Distance oracles
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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