2017/04/20 by Balliu, Alkida, Olivetti, Dennis
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1704.06078
We consider the problem of routing in presence of faults in undirected weighted graphs. More specifically, we focus on the design of compact name-independent fault-tolerant routing schemes, where the designer of the scheme is not allowed to assign names to nodes, i.e., the name of a node is just its identifier. Given a set F of faulty (or forbidden) edges, the goal is to route from a source node s to a target t avoiding the forbidden edges in F. Given any name-dependent fault-tolerant routing scheme and any name-independent routing scheme, we show how to use them as a black box to construct a name-independent fault-tolerant routing scheme. In particular, we present a name-independent routing scheme able to handle any set F of forbidden edges in |F|+1 connected graphs. This has stretch O(k2 |F|3(|F|+log2 n)log D), where D is the diameter of the graph. It uses tables of size \widetildeO(k n1/k(k + deg(v))) bits at every node v, where deg(v) is the degree of node v. In the context of networks that suffer only from occasional failures, we present a name-independent routing scheme that handles only 1 fault at a time, and another routing scheme that handles at most 2 faults at a time. The former uses \widetildeO(k2 n1/k + k deg(v)) bits of memory per node, with stretch O(k3log D). The latter consumes in average \widetildeO(k2 n1/k + deg(v)) bits of memory per node, with stretch O(k2log D).