Easily repairable networks: reconnecting nodes after damage

When networks come under attack, a repairable architecture is superior to, and globally distinct from, an architecture that is robust.

Physical Review Letters 113, 138701 (2014)

R. Farr, J. Harer, T. Fink

Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
LCP
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"
Image for the paper "Easily repairable networks: reconnecting nodes after damage"

We introduce a simple class of distribution networks that withstand damage by being repairable instead of redundant. Instead of asking how hard it is to disconnect nodes through damage, we ask how easy it is to reconnect nodes after damage. We prove that optimal networks on regular lattices have an expected cost of reconnection proportional to the lattice length, and that such networks have exactly three levels of structural hierarchy. We extend our results to networks subject to repeated attacks, in which the repairs themselves must be repairable. We find that, in exchange for a modest increase in repair cost, such networks are able to withstand any number of attacks.