Many modern networks are reconfigurable, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company’s organizational chart; infrastructure networks, such as an airline’s transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call self-healing. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer.
@cite_41: 
@cite_57: Complex networks with a heterogeneous distribution of loads may undergo a global cascade of overload failures when highly loaded nodes or edges are removed due to attacks or failures. Since a small attack or failure has the potential to trigger a global cascade, a fundamental question regards the possible strategies of defense to prevent the cascade from propagating through the entire network. Here we introduce and investigate a costless strategy of defense based on a selective further removal of nodes and edges, right after the initial attack or failure. This intentional removal of network elements is shown to drastically reduce the size of the cascade.
@cite_13: Recent studies of attacks on complex networks suggest that small initial breakdowns can lead to global cascades of overload failures in communication, economic trading, and supply-transportation systems, considering the defense methods is very important to reduce the huge damage. The propagation of failures depends on the flow dynamics such as packet routing of physical quantities and on the heterogeneous distribution of load or capacity in many realistic networks which have topological properties of scale-free (SF) and degree-degree correlations. We introduce a defense strategy based on emergent rewirings between neighbors of the attacked node, and investigate the size of cascade on SF networks with controllable correlations. We show the differences of damaged size for the types of correlations and the effective range of tolerance in the defense methods. They can be performed on the current wireless communication or dynamic allocation technologies.
@cite_23: We investigate growing networks based on Barabasi and Albert's algorithm for generating scale-free networks, but with edges sensitive to overload breakdown. The load is defined through edge betweenness centrality. We focus on the situation where the average number of connections per vertex is, like the number of vertices, linearly increasing in time. After an initial stage of growth, the network undergoes avalanching breakdowns to a fragmented state from which it never recovers. This breakdown is much less violent if the growth is by random rather than by preferential attachment (as defines the Barabasi and Albert model). We briefly discuss the case where the average number of connections per vertex is constant. In this case no breakdown avalanches occur. Implications to the growth of real-world communication networks are discussed.
There has also been recent research in the physics community on preventing cascading failures. In the model used for these results, each vertex in the network starts with a fixed capacity. When a vertex is deleted, some of its load'' (typically defined as the number of shortest paths that go through the vertex) is diverted to the remaining vertices. The remaining vertices, in turn, can fail if the extra load exceeds their capacities. Motter, Lai, Holme, and Kim have shown empirically that even a single node deletion can cause a constant fraction of the nodes to fail in a power-law network due to cascading failures @cite_23 @cite_41 . Motter and Lai propose a strategy for addressing this problem by intentional removal of certain nodes in the network after a failure begins @cite_57 . Hayashi and Miyazaki propose another strategy, called emergent rewirings, that adds edges to the network after a failure begins to prevent the failure from cascading @cite_13 . Both of these approaches are shown to work well empirically on many networks. However, unfortunately, they perform very poorly under adversarial attack.