---
_id: '19827'
abstract:
- lang: eng
  text: "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 degree d¡Ê ¦¸(log n) that a
    series of O(dn) Random k-Flipper operations with k ∈ ¦¨(d2n2 log 1/¦Å) transforms
    any graph into an expander graph with high probability, i.e. 1-n-¦¨(1).\r\n\r\nThe
    Random 1-Flipper is symmetric, i.e. the transformation probability from any labeled
    <i>d</i>-regular graph <i>G</i> to <i>G'</i> is equal to those from <i>G'</i>
    to <i>G</i>. 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 <i>d</i>-regular graphs. For degree <i>d</i>
    ∈ ω(1) growing with the graph size this implies that iteratively applying Random
    1-Flipper transforms any given graph into an expander asymptotically almost surely.\r\n\r\nWe
    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."
author:
- first_name: Peter
  full_name: Mahlmann, Peter
  last_name: Mahlmann
- first_name: Christian
  full_name: Schindelhauer, Christian
  last_name: Schindelhauer
citation:
  ama: 'Mahlmann P, Schindelhauer C. Peer-to-peer networks based on random transformations
    of connected regular undirected graphs. In: <i>Proceedings of the 17th Annual
    ACM Symposium on Parallelism in Algorithms and Architectures  - SPAA’05</i>. ;
    2005. doi:<a href="https://doi.org/10.1145/1073970.1073992">10.1145/1073970.1073992</a>'
  apa: Mahlmann, P., &#38; Schindelhauer, C. (2005). Peer-to-peer networks based on
    random transformations of connected regular undirected graphs. In <i>Proceedings
    of the 17th annual ACM symposium on Parallelism in algorithms and architectures 
    - SPAA’05</i>. <a href="https://doi.org/10.1145/1073970.1073992">https://doi.org/10.1145/1073970.1073992</a>
  bibtex: '@inproceedings{Mahlmann_Schindelhauer_2005, title={Peer-to-peer networks
    based on random transformations of connected regular undirected graphs}, DOI={<a
    href="https://doi.org/10.1145/1073970.1073992">10.1145/1073970.1073992</a>}, booktitle={Proceedings
    of the 17th annual ACM symposium on Parallelism in algorithms and architectures 
    - SPAA’05}, author={Mahlmann, Peter and Schindelhauer, Christian}, year={2005}
    }'
  chicago: Mahlmann, Peter, and Christian Schindelhauer. “Peer-to-Peer Networks Based
    on Random Transformations of Connected Regular Undirected Graphs.” In <i>Proceedings
    of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures 
    - SPAA’05</i>, 2005. <a href="https://doi.org/10.1145/1073970.1073992">https://doi.org/10.1145/1073970.1073992</a>.
  ieee: P. Mahlmann and C. Schindelhauer, “Peer-to-peer networks based on random transformations
    of connected regular undirected graphs,” in <i>Proceedings of the 17th annual
    ACM symposium on Parallelism in algorithms and architectures  - SPAA’05</i>, 2005.
  mla: Mahlmann, Peter, and Christian Schindelhauer. “Peer-to-Peer Networks Based
    on Random Transformations of Connected Regular Undirected Graphs.” <i>Proceedings
    of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures 
    - SPAA’05</i>, 2005, doi:<a href="https://doi.org/10.1145/1073970.1073992">10.1145/1073970.1073992</a>.
  short: 'P. Mahlmann, C. Schindelhauer, in: Proceedings of the 17th Annual ACM Symposium
    on Parallelism in Algorithms and Architectures  - SPAA’05, 2005.'
date_created: 2020-10-01T09:50:59Z
date_updated: 2022-01-06T06:54:13Z
department:
- _id: '63'
doi: 10.1145/1073970.1073992
language:
- iso: eng
publication: Proceedings of the 17th annual ACM symposium on Parallelism in algorithms
  and architectures  - SPAA'05
publication_identifier:
  isbn:
  - '1581139861'
publication_status: published
status: public
title: Peer-to-peer networks based on random transformations of connected regular
  undirected graphs
type: conference
user_id: '15415'
year: '2005'
...