---
_id: '570'
abstract:
- lang: eng
  text: 'This article studies the construction of self-stabilizing topologies for
    distributed systems. While recent research has focused on chain topologies where
    nodes need to be linearized with respect to their identiers, we explore a natural
    and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing
    algorithm DStab which is based on the concept of \local Delaunay graphs" and which
    forwards temporary edges in greedy fashion reminiscent of compass routing. DStab
    constructs a Delaunay graph from any initial connected topology and in a distributed
    manner in time O(n3) in the worst-case; if the initial network contains the Delaunay
    graph, the convergence time is only O(n) rounds. DStab also ensures that individual
    node joins and leaves aect a small part of the network only. Such self-stabilizing
    Delaunay networks have interesting applications and our construction gives insights
    into the necessary geometric reasoning that is required for higherdimensional
    linearization problems.Keywords: Distributed Algorithms, Topology Control, Social
    Networks'
author:
- first_name: Riko
  full_name: Jacob, Riko
  last_name: Jacob
- first_name: Stephan
  full_name: Ritscher, Stephan
  last_name: Ritscher
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological
    self-stabilization: A distributed algorithm for Delaunay graphs. <i>Theoretical
    Computer Science</i>. 2012:137-148. doi:<a href="https://doi.org/10.1016/j.tcs.2012.07.029">10.1016/j.tcs.2012.07.029</a>'
  apa: 'Jacob, R., Ritscher, S., Scheideler, C., &#38; Schmid, S. (2012). Towards
    higher-dimensional topological self-stabilization: A distributed algorithm for
    Delaunay graphs. <i>Theoretical Computer Science</i>, 137–148. <a href="https://doi.org/10.1016/j.tcs.2012.07.029">https://doi.org/10.1016/j.tcs.2012.07.029</a>'
  bibtex: '@article{Jacob_Ritscher_Scheideler_Schmid_2012, title={Towards higher-dimensional
    topological self-stabilization: A distributed algorithm for Delaunay graphs},
    DOI={<a href="https://doi.org/10.1016/j.tcs.2012.07.029">10.1016/j.tcs.2012.07.029</a>},
    journal={Theoretical Computer Science}, publisher={Elsevier}, author={Jacob, Riko
    and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}, year={2012},
    pages={137–148} }'
  chicago: 'Jacob, Riko, Stephan Ritscher, Christian Scheideler, and Stefan Schmid.
    “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm
    for Delaunay Graphs.” <i>Theoretical Computer Science</i>, 2012, 137–48. <a href="https://doi.org/10.1016/j.tcs.2012.07.029">https://doi.org/10.1016/j.tcs.2012.07.029</a>.'
  ieee: 'R. Jacob, S. Ritscher, C. Scheideler, and S. Schmid, “Towards higher-dimensional
    topological self-stabilization: A distributed algorithm for Delaunay graphs,”
    <i>Theoretical Computer Science</i>, pp. 137–148, 2012.'
  mla: 'Jacob, Riko, et al. “Towards Higher-Dimensional Topological Self-Stabilization:
    A Distributed Algorithm for Delaunay Graphs.” <i>Theoretical Computer Science</i>,
    Elsevier, 2012, pp. 137–48, doi:<a href="https://doi.org/10.1016/j.tcs.2012.07.029">10.1016/j.tcs.2012.07.029</a>.'
  short: R. Jacob, S. Ritscher, C. Scheideler, S. Schmid, Theoretical Computer Science
    (2012) 137–148.
date_created: 2017-10-17T12:42:43Z
date_updated: 2022-01-06T07:02:36Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1016/j.tcs.2012.07.029
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:16:20Z
  date_updated: 2018-03-15T10:16:20Z
  file_id: '1272'
  file_name: 570-Delaunay-Journal.pdf
  file_size: 250051
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:16:20Z
has_accepted_license: '1'
page: 137-148
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Theoretical Computer Science
publisher: Elsevier
status: public
title: 'Towards higher-dimensional topological self-stabilization: A distributed algorithm
  for Delaunay graphs'
type: journal_article
user_id: '477'
year: '2012'
...