Yaron Weinsberg, Danny Dolev, et al.
EuroSys 2008
Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing p for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,ρ)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if p is a minimal length routing, then the diameter of R(G, ρ)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G, ρ)/F<3 for any minimal length routing p and any set of faults F with IFl<n. We also show that if F consists only of edges and does not disconnect G, then the diameter of R(G, ρ)/F is < 3IFI+1, while if F consists only of nodes and does not disconnect G, then the diameter of R(G, ρ)/F is < the sum of the degrees of the nodes in F, where in both cases ρ is an arbitrary minimal length routing. We conclude with one of the most important contributions of this paper: a list of interesting and apparently difficult open problems.
Yaron Weinsberg, Danny Dolev, et al.
EuroSys 2008
B. Awerbuch, A. Israeli, et al.
STOC 1984
Danny Bickson, Tzachy Reinman, et al.
Peer-to-Peer Networking and Applications
Danny Dolev, Nir Shavit
SIAM Journal on Computing