We present k-Flipper, a graph transformation algorithm that transforms regular undirected graphs. Given a path of k + 2 edges it interchanges the end vertices of the path. By definition this operation preserves regularity and connectivity. We show that every regular connected graph can be reached by a series of these operations for all k ≥ 1. We use a randomized version, called Random k-Flipper, in order to create random regular connected undirected graphs that may serve as a backbone for peer-to-peer networks. We prove for de- 2 log 1/ ) transforms any graph into an expander graph with high probability, i.e. 1−n −Θ(1) . The Random 1-Flipper is symmetric, i.e. the transformation probability from any labeled d-regular graph G to G is equal to those from G to G. From this and the reachability property we conclude that in the limit a series of Random 1-Flipper operations converges against an uniform probability distribution over all connected labeled d-regular graphs. For degree d ∈ ω(1) growing with the graph size this implies that iteratively applying Random 1-Flipper transforms any given graph into an expander asymptotically almost surely. We use these operations as a maintenance operation for a peer-to-peer network based on random regular connected graphs that provides high robustness and recovers from degenerate network structures by continuously applying these random graph transformations. For this, we describe how network operations for joining and leaving the network can be designed and how the concurrency of the graph transformations can be handled.
Initially, Mahlmann and Schindelhauer have proposed Random k-Flipper REF , a graph transformation algorithm that creates random regular connected undirected graphs, asymptotically almost surely uniform.
Peer-to-peer networks based on random transformations of connected regular undirected graphs
SPAA '05
Computer Science