2026-07-23T21:43:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13124 2024-03-06T10:51:37Z ddc:004 open_access

Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally Foerster, Klaus-Tycho Hirvonen, Juho Pignolet, Yvonne-Anne Schmid, Stefan Tredan, Gilles Resilience Local Failover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus-Tycho Foerster and Juho Hirvonen and Yvonne-Anne Pignolet and Stefan Schmid and Gilles Tredan 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.46 urn:nbn:de:0030-drops-131244 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.46 eng https://creativecommons.org/licenses/by/3.0/legalcode