Network Researchers Nail Down Theory of ‘Perfect Resilience’
Introduction
One evening in the fall of 1969, a team of researchers sent a historic message from a computer in Los Angeles to one in Menlo Park, California. Or rather, they sent part of the message: the “L” and “O” in “LOGIN.” The first transmission over the first link in Arpanet, the prototype for the modern internet, lasted all of two characters before the network crashed.
Computer networks have grown much more reliable since that first test nearly 60 years ago. But we also demand a lot more of them. When you watch a movie online, the video data gets divided into a series of tiny “packets” that hop between way stations called routers on their way to your computer. Links between routers sometimes fail. One reason our videos aren’t constantly glitching out is that each router has a thorough contingency plan — a set of rules for redirecting packets in case a link goes down.
If a large outage cuts off every path between two points, there’s no way a packet can get through. But ideally, a network would be able to withstand any pattern of link failures short of this worst-case scenario. Researchers call this property “perfect resilience.” For over a decade, computer scientists have sought to understand what kinds of networks can be made perfectly resilient under realistic conditions.
Now, in a paper that was presented at the Symposium on Theory of Computing in June 2026, two researchers have settled the question with a comprehensive proof. They showed that there are exactly four minimal network structures that can thwart perfect resilience. In networks that lack these structures, you can always concoct rules that will reliably deliver packets from any source to any destination, regardless of which links fail.
“It’s a very elegant contribution,” said Michael Schapira, a computer scientist at the Hebrew University of Jerusalem who was not involved in the result. “It’s pretty rare that you get a complete understanding of something.”
Think Globally, Act Locally
Imagine you have a network of routers in which each device can direct data packets bound for any other point in the network. You can then ask yourself: What instructions should the routers follow?
One simple approach would be to map out the shortest path between every pair of points in the network, and then give each router a copy of the map. If the network ever changes — if even a single link fails — start over and do it again.
In principle, this strategy will ensure that every packet reaches its destination. In practice, it’s far too slow. Calculating shortest paths is inherently a “global” problem — it requires knowledge of the entire network. In a real-world network, that calculation might take up to a few seconds. But each router has to act fast, in a fraction of a millisecond or less. That means routers must direct packets using only locally accessible information, such as the status of links to their immediate neighbors.
This restriction makes the problem of perfect resilience much more complicated. Without any global coordination between routers, packets might get trapped in loops.
In a 2012 paper, Schapira and five other researchers formally defined perfect resilience and devised a mathematical model to study when it’s achievable. They assumed that routing rules must have a simple form. A router can decide in which direction to send each new packet using only three factors: the packet’s destination, the link it arrived on, and which neighboring links have failed. The rules can’t depend on the path that a packet has taken so far, since routers don’t have access to this information.
With these assumptions, the researchers aimed to capture “something very close to how networks actually operate,” said Brighten Godfrey, a computer scientist at the University of Illinois, Urbana-Champaign who co-authored the 2012 paper.
In 2020, Stefan Schmid and his colleagues proved a partial result about the reliability of communication networks.
Christian Kielmann
Godfrey, Schapira, and their colleagues showed that in this model, perfect resilience isn’t always achievable. They did so by finding a single example of a network layout that can’t be made perfectly resilient. No matter what set of routing rules you choose, there’s always a pattern of link failures that will cause some packets to get stuck in a loop.
But the network they identified was fairly complicated. Was it a rare example? Or is perfect resilience impossible in many other networks as well?
Minor Problems
The 2012 paper caught the attention of Stefan Schmid, a networking researcher now at the Technical University of Berlin. He toyed with the perfect-resilience problem on and off for years, but his first real progress came in 2020, when he and his colleagues made a connection to a topic in mathematics called the theory of graph minors.
Computer scientists have long studied the mathematical properties of real-world networks by modeling them as graphs — webs of nodes connected by lines called edges. Imagine that you start with a graph, then repeatedly simplify it using three basic operations: You can delete a node, delete an edge, or merge pairs of connected nodes. The graphs that you can obtain by combining these operations are known as the minors of the larger graph.
Mark Belan/Quanta Magazine
These operations never make it more likely that packets will get routed in endless loops. If a graph is perfectly resilient, then so are all of its minors.
You can reverse this logic and understand the behavior of large, complex graphs using the properties of their simpler minors. An iconic result in graph theory, called the Robertson-Seymour theorem, tells you what you can learn from this kind of reversal. Applied to network resilience, the theorem states that there’s only a finite number of minors that are not perfectly resilient — every larger graph that lacks perfect resilience reduces to one of these so-called forbidden minors. If you can identify the full set of forbidden minors, you’ll have a complete understanding of when perfect resilience is achievable.
Unfortunately, the Robertson-Seymour theorem doesn’t tell you how many forbidden minors there are, or how to find them. “We know such a finite set exists,” said Matthias Bentert, a theoretical computer scientist at the Technical University of Berlin and Schmid’s collaborator on the new paper. “But we don’t know, does it contain one or two graphs, or does it contain 100,000 graphs?”
Matthias Bentert, an expert in the math of graph theory, teamed up with Schmid to complete a comprehensive proof.
Alexander Maack
The researchers wanted to find the complete set of forbidden minors and prove that no others existed.
In their 2020 paper, Schmid and his colleagues identified two simple graph minors that prevent perfect resilience, but then they got stuck. Schmid suspected they’d need a collaborator with more expertise in graph theory to make further progress. Three years later, he met Bentert at a research retreat, and they worked together briefly on a different problem. In 2025, when Bentert was wrapping up a postdoctoral fellowship in Norway, Schmid invited him to join his group in Berlin.
“It was a really perfect match,” Schmid said. “Matthias made a lot of very fast contributions on a couple of our problems.” Perhaps he’d help make quick work of the perfect-resilience problem, too.
Escaping the Maze
Bentert quickly identified a third forbidden minor. He then decided to see how far he could get by attacking the problem from the other direction. Perhaps if there were no additional forbidden minors — if the three they had found were the complete set — then he could prove that all graphs that lacked these three could be made perfectly resilient.
The strategy worked, but not in the way he had hoped. “I found that, actually, I cannot show it, because it’s not true,” Bentert said. He had discovered a fourth obstruction.
So now they had four forbidden graph structures. Were there more? Bentert tried the same strategy again: Prove that all graphs that lacked these four minors could be made perfectly resilient. The strategy worked, this time because he really had found the full set.
The four forbidden graph minors.
Bentert hadn’t expected the answer to be so simple. “I would have stopped if I reached 50 or so, but that it’s really only four was a little bit of a surprise to me,” he said.
Of course, knowing that perfect resilience is theoretically achievable for any given network is only useful if you know how to choose the right routing rules. Fortunately, Schmid and Bentert’s new result also yields a fast algorithm for finding these rules, which turn out to take a similar form in any network. They’re all based on a trick for escaping mazes: Simply take a right turn at every intersection. The only networks where a maze navigation–based approach fails are those containing one of the four forbidden minors. For those networks, changing the rules won’t help.
Real-World Resilience
With their new result, Schmid and Bentert have fully resolved the perfect-resilience problem as it was originally posed in 2012. But the solution isn’t all good news. Even though there are only four graph structures that obstruct perfect resilience, the fact that they’re so simple means that many networks will have them as minors. Dense networks with many connections are especially likely to lack perfect resilience — an ironic outcome, given that adding more links to a network is the most straightforward way to make it more reliable.
“The more connectivity you have, the more possible subgraphs there are,” Godfrey said. “I wouldn’t be surprised if many real-world networks do not have a solution for perfect resilience.”
That may not be a deal-breaker: In some communication networks, resilience isn’t as critical as high speed and low congestion, two factors that Schmid and Bentert’s rules don’t take into account. And in cases where resilience is important, Schmid and Bentert’s result may not be the end of the story. They now plan to study how the situation changes if each packet can carry a record of the last few nodes it visited. Bentert is optimistic that this approach could make perfect resilience achievable for a broader range of networks, yet still remain feasible in the real world.
“Maybe some very freaky networks will not be perfectly resilient” even in a modified version of the problem, he said. “But everything that will ever be designed by a human or a machine will be.”