---
_id: '378'
abstract:
- lang: eng
  text: The Chord peer-to-peer system is considered, together with CAN, Tapestry and
    Pastry, as one of the pioneering works on peer-to-peer distributed hash tables
    (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer
    systems in general. Chord, in particular, has been studied thoroughly, and many
    variants of Chord have been presented that optimize various criteria. Also, several
    implementations of Chord are available on various platforms. Though Chord is known
    to be very efficient and scalable and it can handle churn quite well, no protocol
    is known yet that guarantees that Chord is self-stabilizing, i.e., the Chord network
    can be recovered from any initial state in which the network is still weakly connected.
    This is not too surprising since it is known that the Chord network is not locally
    checkable for its current topology. We present a slight extension of the Chord
    network, called Re-Chord (reactive Chord), that turns out to be locally checkable,
    and we present a self-stabilizing distributed protocol for it that can recover
    the Re-Chord network from any initial state, in which the n peers are weakly connected,
    in O(nlogn) communication rounds. We also show that our protocol allows a new
    peer to join or an old peer to leave an already stable Re-Chord network so that
    within O(logn)^2) communication rounds the Re-Chord network is stable again.
author:
- first_name: Sebastian
  full_name: Kniesburges, Sebastian
  last_name: Kniesburges
- first_name: Andreas
  full_name: Koutsopoulos, Andreas
  last_name: Koutsopoulos
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Kniesburges S, Koutsopoulos A, Scheideler C. Re-Chord: A Self-stabilizing
    Chord Overlay Network. <i>Theory of Computing Systems</i>. 2014;(3):591-612. doi:<a
    href="https://doi.org/10.1007/s00224-012-9431-2">10.1007/s00224-012-9431-2</a>'
  apa: 'Kniesburges, S., Koutsopoulos, A., &#38; Scheideler, C. (2014). Re-Chord:
    A Self-stabilizing Chord Overlay Network. <i>Theory of Computing Systems</i>,
    (3), 591–612. <a href="https://doi.org/10.1007/s00224-012-9431-2">https://doi.org/10.1007/s00224-012-9431-2</a>'
  bibtex: '@article{Kniesburges_Koutsopoulos_Scheideler_2014, title={Re-Chord: A Self-stabilizing
    Chord Overlay Network}, DOI={<a href="https://doi.org/10.1007/s00224-012-9431-2">10.1007/s00224-012-9431-2</a>},
    number={3}, journal={Theory of Computing Systems}, publisher={Springer}, author={Kniesburges,
    Sebastian and Koutsopoulos, Andreas and Scheideler, Christian}, year={2014}, pages={591–612}
    }'
  chicago: 'Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler.
    “Re-Chord: A Self-Stabilizing Chord Overlay Network.” <i>Theory of Computing Systems</i>,
    no. 3 (2014): 591–612. <a href="https://doi.org/10.1007/s00224-012-9431-2">https://doi.org/10.1007/s00224-012-9431-2</a>.'
  ieee: 'S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “Re-Chord: A Self-stabilizing
    Chord Overlay Network,” <i>Theory of Computing Systems</i>, no. 3, pp. 591–612,
    2014.'
  mla: 'Kniesburges, Sebastian, et al. “Re-Chord: A Self-Stabilizing Chord Overlay
    Network.” <i>Theory of Computing Systems</i>, no. 3, Springer, 2014, pp. 591–612,
    doi:<a href="https://doi.org/10.1007/s00224-012-9431-2">10.1007/s00224-012-9431-2</a>.'
  short: S. Kniesburges, A. Koutsopoulos, C. Scheideler, Theory of Computing Systems
    (2014) 591–612.
date_created: 2017-10-17T12:42:05Z
date_updated: 2022-01-06T06:59:35Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/s00224-012-9431-2
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T07:13:36Z
  date_updated: 2018-03-20T07:13:36Z
  file_id: '1396'
  file_name: 378-re-chord_journal.pdf
  file_size: 310961
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T07:13:36Z
has_accepted_license: '1'
issue: '3'
page: 591-612
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Theory of Computing Systems
publisher: Springer
status: public
title: 'Re-Chord: A Self-stabilizing Chord Overlay Network'
type: journal_article
user_id: '477'
year: '2014'
...