---
_id: '125'
abstract:
- lang: eng
  text: 'Searching for other participants is one of the most important operations
    in a distributed system.We are interested in topologies in which it is possible
    to route a packet in a fixed number of hops until it arrives at its destination.Given
    a constant $d$, this paper introduces a new self-stabilizing protocol for the
    $q$-ary $d$-dimensional de Bruijn graph ($q = \sqrt[d]{n}$) that is able to route
    any search request in at most $d$ hops w.h.p., while significantly lowering the
    node degree compared to the clique: We require nodes to have a degree of $\mathcal
    O(\sqrt[d]{n})$, which is asymptotically optimal for a fixed diameter $d$.The
    protocol keeps the expected amount of edge redirections per node in $\mathcal
    O(\sqrt[d]{n})$, when the number of nodes in the system increases by factor $2^d$.The
    number of messages that are periodically sent out by nodes is constant.'
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Feldmann M, Scheideler C. A Self-Stabilizing General De Bruijn Graph. In:
    <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and
    Security of Distributed Systems (SSS)</i>. Vol 10616. Lecture Notes in Computer
    Science. Springer, Cham; 2017:250-264. doi:<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a>'
  apa: Feldmann, M., &#38; Scheideler, C. (2017). A Self-Stabilizing General De Bruijn
    Graph. In <i>Proceedings of the 19th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i> (Vol. 10616, pp. 250–264).
    Springer, Cham. <a href="https://doi.org/10.1007/978-3-319-69084-1_17">https://doi.org/10.1007/978-3-319-69084-1_17</a>
  bibtex: '@inproceedings{Feldmann_Scheideler_2017, series={Lecture Notes in Computer
    Science}, title={A Self-Stabilizing General De Bruijn Graph}, volume={10616},
    DOI={<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a>},
    booktitle={Proceedings of the 19th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann,
    Michael and Scheideler, Christian}, year={2017}, pages={250–264}, collection={Lecture
    Notes in Computer Science} }'
  chicago: Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General
    De Bruijn Graph.” In <i>Proceedings of the 19th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>, 10616:250–64. Lecture Notes
    in Computer Science. Springer, Cham, 2017. <a href="https://doi.org/10.1007/978-3-319-69084-1_17">https://doi.org/10.1007/978-3-319-69084-1_17</a>.
  ieee: M. Feldmann and C. Scheideler, “A Self-Stabilizing General De Bruijn Graph,”
    in <i>Proceedings of the 19th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, 2017, vol. 10616, pp. 250–264.
  mla: Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De
    Bruijn Graph.” <i>Proceedings of the 19th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>, vol. 10616, Springer, Cham,
    2017, pp. 250–64, doi:<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a>.
  short: 'M. Feldmann, C. Scheideler, in: Proceedings of the 19th International Symposium
    on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer,
    Cham, 2017, pp. 250–264.'
date_created: 2017-10-17T12:41:16Z
date_updated: 2022-01-06T06:51:19Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-319-69084-1_17
external_id:
  arxiv:
  - '1708.06542'
file:
- access_level: closed
  content_type: application/pdf
  creator: mfeldma2
  date_created: 2018-10-31T13:30:13Z
  date_updated: 2018-10-31T13:30:13Z
  file_id: '5214'
  file_name: Feldmann-Scheideler2017_Chapter_ASelf-stabilizingGeneralDeBrui.pdf
  file_size: 311204
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T13:30:13Z
has_accepted_license: '1'
intvolume: '     10616'
language:
- iso: eng
page: '250-264 '
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 19th International Symposium on Stabilization, Safety,
  and Security of Distributed Systems (SSS)
publication_identifier:
  isbn:
  - 978-3-319-69083-4
publication_status: published
publisher: Springer, Cham
series_title: Lecture Notes in Computer Science
status: public
title: A Self-Stabilizing General De Bruijn Graph
type: conference
user_id: '23538'
volume: 10616
year: '2017'
...