r~3: Resilient Random Regular Graphs

摘要

Efficiently building and maintaining resilient regular graphs is important for many applications. Such graphs must be easy to build and maintain in the presence of node additions and deletions. They must also have high resilience (connectivity). Typically, algorithms use offline techniques to build regular graphs with strict bounds on resilience and such techniques are not designed to maintain these properties in the presence of online additions, deletions and failures. On the other hand, random regular graphs are easy to construct and maintain, and provide good properties with high probability, but without strict guarantees. In this paper, we introduce a new class of graphs that we call r~3 (resilient random regular) graphs and present a technique to create and maintain r~3 graphs. The r~3 graphs meld the desirable properties of random regular graphs and regular graphs with strict structural properties: they are efficient to create and maintain, and additionally, are highly connected (i.e., 1 + d/2-node and d-edge connected in the worst case). We present the graph building and maintenance techniques, present proofs for graph connectedness, and various properties of r~3 graphs. We believe that r~3 graphs will be useful in many communication applications.