---
_id: '28917'
author:
- first_name: Michael
  full_name: Feldmann, Michael
  last_name: Feldmann
- first_name: Andreas
  full_name: Padalkin, Andreas
  id: '88238'
  last_name: Padalkin
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Shlomi
  full_name: Dolev, Shlomi
  last_name: Dolev
citation:
  ama: 'Feldmann M, Padalkin A, Scheideler C, Dolev S. Coordinating Amoebots via Reconfigurable
    Circuits. In: Johnen C, Michael Schiller E, Schmid S, eds. <i>Stabilization, Safety,
    and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021,
    Virtual Event, November 17-20, 2021, Proceedings</i>. Vol 13046. Lecture Notes
    in Computer Science. Springer; 2021:484-488. doi:<a href="https://doi.org/10.1007/978-3-030-91081-5\_34">10.1007/978-3-030-91081-5\_34</a>'
  apa: Feldmann, M., Padalkin, A., Scheideler, C., &#38; Dolev, S. (2021). Coordinating
    Amoebots via Reconfigurable Circuits. In C. Johnen, E. Michael Schiller, &#38;
    S. Schmid (Eds.), <i>Stabilization, Safety, and Security of Distributed Systems
    - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021,
    Proceedings</i> (Vol. 13046, pp. 484–488). Springer. <a href="https://doi.org/10.1007/978-3-030-91081-5\_34">https://doi.org/10.1007/978-3-030-91081-5\_34</a>
  bibtex: '@inproceedings{Feldmann_Padalkin_Scheideler_Dolev_2021, series={Lecture
    Notes in Computer Science}, title={Coordinating Amoebots via Reconfigurable Circuits},
    volume={13046}, DOI={<a href="https://doi.org/10.1007/978-3-030-91081-5\_34">10.1007/978-3-030-91081-5\_34</a>},
    booktitle={Stabilization, Safety, and Security of Distributed Systems - 23rd International
    Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings}, publisher={Springer},
    author={Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and
    Dolev, Shlomi}, editor={Johnen, Colette and Michael Schiller, Elad and Schmid,
    Stefan}, year={2021}, pages={484–488}, collection={Lecture Notes in Computer Science}
    }'
  chicago: Feldmann, Michael, Andreas Padalkin, Christian Scheideler, and Shlomi Dolev.
    “Coordinating Amoebots via Reconfigurable Circuits.” In <i>Stabilization, Safety,
    and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021,
    Virtual Event, November 17-20, 2021, Proceedings</i>, edited by Colette Johnen,
    Elad Michael Schiller, and Stefan Schmid, 13046:484–88. Lecture Notes in Computer
    Science. Springer, 2021. <a href="https://doi.org/10.1007/978-3-030-91081-5\_34">https://doi.org/10.1007/978-3-030-91081-5\_34</a>.
  ieee: 'M. Feldmann, A. Padalkin, C. Scheideler, and S. Dolev, “Coordinating Amoebots
    via Reconfigurable Circuits,” in <i>Stabilization, Safety, and Security of Distributed
    Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20,
    2021, Proceedings</i>, 2021, vol. 13046, pp. 484–488, doi: <a href="https://doi.org/10.1007/978-3-030-91081-5\_34">10.1007/978-3-030-91081-5\_34</a>.'
  mla: Feldmann, Michael, et al. “Coordinating Amoebots via Reconfigurable Circuits.”
    <i>Stabilization, Safety, and Security of Distributed Systems - 23rd International
    Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings</i>, edited
    by Colette Johnen et al., vol. 13046, Springer, 2021, pp. 484–88, doi:<a href="https://doi.org/10.1007/978-3-030-91081-5\_34">10.1007/978-3-030-91081-5\_34</a>.
  short: 'M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, in: C. Johnen, E. Michael
    Schiller, S. Schmid (Eds.), Stabilization, Safety, and Security of Distributed
    Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20,
    2021, Proceedings, Springer, 2021, pp. 484–488.'
date_created: 2021-12-15T09:37:38Z
date_updated: 2022-01-06T06:58:41Z
department:
- _id: '79'
doi: 10.1007/978-3-030-91081-5\_34
editor:
- first_name: Colette
  full_name: Johnen, Colette
  last_name: Johnen
- first_name: Elad
  full_name: Michael Schiller, Elad
  last_name: Michael Schiller
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
intvolume: '     13046'
language:
- iso: eng
page: 484-488
publication: Stabilization, Safety, and Security of Distributed Systems - 23rd International
  Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Coordinating Amoebots via Reconfigurable Circuits
type: conference
user_id: '15504'
volume: 13046
year: '2021'
...
---
_id: '28998'
author:
- first_name: Dennis
  full_name: Suermann, Dennis
  last_name: Suermann
citation:
  ama: Suermann D. <i>Schutz Und Stabilisierung von Overlay-Netzwerken Mithilfe Des
    Relay-Layers</i>.; 2021.
  apa: Suermann, D. (2021). <i>Schutz und Stabilisierung von Overlay-Netzwerken mithilfe
    des Relay-Layers</i>.
  bibtex: '@book{Suermann_2021, title={Schutz und Stabilisierung von Overlay-Netzwerken
    mithilfe des Relay-Layers}, author={Suermann, Dennis}, year={2021} }'
  chicago: Suermann, Dennis. <i>Schutz Und Stabilisierung von Overlay-Netzwerken Mithilfe
    Des Relay-Layers</i>, 2021.
  ieee: D. Suermann, <i>Schutz und Stabilisierung von Overlay-Netzwerken mithilfe
    des Relay-Layers</i>. 2021.
  mla: Suermann, Dennis. <i>Schutz Und Stabilisierung von Overlay-Netzwerken Mithilfe
    Des Relay-Layers</i>. 2021.
  short: D. Suermann, Schutz Und Stabilisierung von Overlay-Netzwerken Mithilfe Des
    Relay-Layers, 2021.
date_created: 2021-12-16T06:41:25Z
date_updated: 2022-01-06T06:58:43Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Schutz und Stabilisierung von Overlay-Netzwerken mithilfe des Relay-Layers
type: bachelorsthesis
user_id: '15504'
year: '2021'
...
---
_id: '27053'
author:
- first_name: Leon
  full_name: Everling, Leon
  last_name: Everling
citation:
  ama: Everling L. <i>Selbststabilisierender Bakery Algorithmus Für Verteilte Systeme</i>.;
    2021.
  apa: Everling, L. (2021). <i>Selbststabilisierender Bakery Algorithmus für verteilte
    Systeme</i>.
  bibtex: '@book{Everling_2021, title={Selbststabilisierender Bakery Algorithmus für
    verteilte Systeme}, author={Everling, Leon}, year={2021} }'
  chicago: Everling, Leon. <i>Selbststabilisierender Bakery Algorithmus Für Verteilte
    Systeme</i>, 2021.
  ieee: L. Everling, <i>Selbststabilisierender Bakery Algorithmus für verteilte Systeme</i>.
    2021.
  mla: Everling, Leon. <i>Selbststabilisierender Bakery Algorithmus Für Verteilte
    Systeme</i>. 2021.
  short: L. Everling, Selbststabilisierender Bakery Algorithmus Für Verteilte Systeme,
    2021.
date_created: 2021-11-02T10:13:51Z
date_updated: 2022-01-06T06:57:33Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Selbststabilisierender Bakery Algorithmus für verteilte Systeme
type: bachelorsthesis
user_id: '15504'
year: '2021'
...
---
_id: '27072'
author:
- first_name: Vaibhav
  full_name: Adsul, Vaibhav
  last_name: Adsul
citation:
  ama: Adsul V. <i>Peer-to-Peer Matching for Distributed Systems</i>.; 2021.
  apa: Adsul, V. (2021). <i>Peer-to-Peer Matching for Distributed Systems</i>.
  bibtex: '@book{Adsul_2021, title={Peer-to-Peer Matching for Distributed Systems},
    author={Adsul, Vaibhav}, year={2021} }'
  chicago: Adsul, Vaibhav. <i>Peer-to-Peer Matching for Distributed Systems</i>, 2021.
  ieee: V. Adsul, <i>Peer-to-Peer Matching for Distributed Systems</i>. 2021.
  mla: Adsul, Vaibhav. <i>Peer-to-Peer Matching for Distributed Systems</i>. 2021.
  short: V. Adsul, Peer-to-Peer Matching for Distributed Systems, 2021.
date_created: 2021-11-03T06:12:47Z
date_updated: 2022-01-06T06:57:33Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Peer-to-Peer Matching for Distributed Systems
type: mastersthesis
user_id: '15504'
year: '2021'
...
---
_id: '21084'
author:
- first_name: Julian
  full_name: Werthmann, Julian
  id: '50024'
  last_name: Werthmann
citation:
  ama: Werthmann J. <i>Derandomization and Local Graph Problems in the Node-Capacitated
    Clique</i>.; 2021.
  apa: Werthmann, J. (2021). <i>Derandomization and Local Graph Problems in the Node-Capacitated
    Clique</i>.
  bibtex: '@book{Werthmann_2021, title={Derandomization and Local Graph Problems in
    the Node-Capacitated Clique}, author={Werthmann, Julian}, year={2021} }'
  chicago: Werthmann, Julian. <i>Derandomization and Local Graph Problems in the Node-Capacitated
    Clique</i>, 2021.
  ieee: J. Werthmann, <i>Derandomization and Local Graph Problems in the Node-Capacitated
    Clique</i>. 2021.
  mla: Werthmann, Julian. <i>Derandomization and Local Graph Problems in the Node-Capacitated
    Clique</i>. 2021.
  short: J. Werthmann, Derandomization and Local Graph Problems in the Node-Capacitated
    Clique, 2021.
date_created: 2021-01-26T13:58:14Z
date_updated: 2022-01-06T06:54:44Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Derandomization and Local Graph Problems in the Node-Capacitated Clique
type: mastersthesis
user_id: '15504'
year: '2021'
...
---
_id: '21197'
author:
- first_name: Ma
  full_name: Mengshi, Ma
  last_name: Mengshi
citation:
  ama: Mengshi M. <i>Self-Stabilizing Arrow Protocol on Spanning Trees with a Low
    Diameter</i>.; 2021.
  apa: Mengshi, M. (2021). <i>Self-stabilizing Arrow Protocol on Spanning Trees with
    a Low Diameter</i>.
  bibtex: '@book{Mengshi_2021, title={Self-stabilizing Arrow Protocol on Spanning
    Trees with a Low Diameter}, author={Mengshi, Ma}, year={2021} }'
  chicago: Mengshi, Ma. <i>Self-Stabilizing Arrow Protocol on Spanning Trees with
    a Low Diameter</i>, 2021.
  ieee: M. Mengshi, <i>Self-stabilizing Arrow Protocol on Spanning Trees with a Low
    Diameter</i>. 2021.
  mla: Mengshi, Ma. <i>Self-Stabilizing Arrow Protocol on Spanning Trees with a Low
    Diameter</i>. 2021.
  short: M. Mengshi, Self-Stabilizing Arrow Protocol on Spanning Trees with a Low
    Diameter, 2021.
date_created: 2021-02-09T07:09:22Z
date_updated: 2022-01-06T06:54:49Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '13'
  name: SFB 901 - Subproject C1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Self-stabilizing Arrow Protocol on Spanning Trees with a Low Diameter
type: bachelorsthesis
user_id: '15504'
year: '2021'
...
---
_id: '21627'
author:
- first_name: David
  full_name: Liedtke, David
  last_name: Liedtke
citation:
  ama: Liedtke D. <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>.; 2021.
  apa: Liedtke, D. (2021). <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>.
  bibtex: '@book{Liedtke_2021, title={Exploration and Convex Hull Construction in
    the Three-Dimensional Hybrid Model}, author={Liedtke, David}, year={2021} }'
  chicago: Liedtke, David. <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>, 2021.
  ieee: D. Liedtke, <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>. 2021.
  mla: Liedtke, David. <i>Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model</i>. 2021.
  short: D. Liedtke, Exploration and Convex Hull Construction in the Three-Dimensional
    Hybrid Model, 2021.
date_created: 2021-04-15T05:51:43Z
date_updated: 2022-01-06T06:55:08Z
department:
- _id: '79'
language:
- iso: eng
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model
type: mastersthesis
user_id: '15504'
year: '2021'
...
---
_id: '21628'
abstract:
- lang: eng
  text: "This thesis considers the realization of distributed data structures and
    the construction of distributed protocols for self-stabilizing overlay networks.\r\n\r\nIn
    the first part of this thesis, we provide distributed protocols for queues, stacks
    and priority queues that serve the insertion and deletion of elements within a
    logarithmic amount of rounds.\r\nOur protocols respect semantic constraints such
    as sequential consistency or serializability and the individual semantic constraints
    given by the type (queue, stack, priority queue) of the data structure.\r\nWe
    furthermore provide a protocol that handles joining and leaving nodes.\r\nAs an
    important side product, we present a novel protocol solving the distributed $k$-selection
    problem in a logarithmic amount of rounds, that is, to find the $k$-smallest elements
    among a polynomial number of elements spread among $n$ nodes.\r\n\t\r\nThe second
    part of this thesis is devoted to the construction of protocols for self-stabilizing
    overlay networks, i.e., distributed protocols that transform an overlay network
    from any initial (potentially illegitimate) state into a legitimate state in finite
    time.\r\nWe present protocols for self-stabilizing generalized De Bruijn graphs,
    self-stabilizing quadtrees and self-stabilizing supervised skip rings.\r\nEach
    of those protocols comes with unique properties that makes it interesting for
    certain distributed applications.\r\nGeneralized De Bruijn networks provide routing
    within a constant amount of hops, thus serving the interest in networks that require
    a low latency for requests.\r\nThe protocol for the quadtree guarantees monotonic
    searchability as well as a geometric variant of monotonic searchability, making
    it interesting for wireless networks or applications needed in the area of computational
    geometry.\r\nThe supervised skip ring can be used to construct a self-stabilizing
    publish-subscribe system.\r\n"
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
citation:
  ama: Feldmann M. <i>Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks</i>.; 2021. doi:<a href="https://doi.org/10.17619/UNIPB/1-1113">10.17619/UNIPB/1-1113</a>
  apa: Feldmann, M. (2021). <i>Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks</i>. <a href="https://doi.org/10.17619/UNIPB/1-1113">https://doi.org/10.17619/UNIPB/1-1113</a>
  bibtex: '@book{Feldmann_2021, title={Algorithms for Distributed Data Structures
    and Self-Stabilizing Overlay Networks}, DOI={<a href="https://doi.org/10.17619/UNIPB/1-1113">10.17619/UNIPB/1-1113</a>},
    author={Feldmann, Michael}, year={2021} }'
  chicago: Feldmann, Michael. <i>Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks</i>, 2021. <a href="https://doi.org/10.17619/UNIPB/1-1113">https://doi.org/10.17619/UNIPB/1-1113</a>.
  ieee: M. Feldmann, <i>Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks</i>. 2021.
  mla: Feldmann, Michael. <i>Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks</i>. 2021, doi:<a href="https://doi.org/10.17619/UNIPB/1-1113">10.17619/UNIPB/1-1113</a>.
  short: M. Feldmann, Algorithms for Distributed Data Structures and Self-Stabilizing
    Overlay Networks, 2021.
date_created: 2021-04-15T08:23:52Z
date_updated: 2022-01-06T06:55:08Z
ddc:
- '006'
department:
- _id: '79'
doi: 10.17619/UNIPB/1-1113
file:
- access_level: closed
  content_type: application/pdf
  creator: mfeldma2
  date_created: 2021-04-15T08:21:15Z
  date_updated: 2021-04-15T08:21:15Z
  file_id: '21629'
  file_name: Dissertation_Michael_Feldmann.pdf
  file_size: 2617069
  relation: main_file
  success: 1
file_date_updated: 2021-04-15T08:21:15Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Algorithms for Distributed Data Structures and Self-Stabilizing Overlay Networks
type: dissertation
user_id: '23538'
year: '2021'
...
---
_id: '30217'
author:
- first_name: Sam
  full_name: Coy, Sam
  last_name: Coy
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Michael
  full_name: Feldmann, Michael
  last_name: Feldmann
- first_name: Kristian
  full_name: Hinnenthal, Kristian
  last_name: Hinnenthal
- first_name: Fabian
  full_name: Kuhn, Fabian
  last_name: Kuhn
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Philipp
  full_name: Schneider, Philipp
  last_name: Schneider
- first_name: Martijn
  full_name: Struijs, Martijn
  last_name: Struijs
citation:
  ama: 'Coy S, Czumaj A, Feldmann M, et al. Near-Shortest Path Routing in Hybrid Communication
    Networks. In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference
    on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg,
    France</i>. Vol 217. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2021:11:1–11:23. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">10.4230/LIPIcs.OPODIS.2021.11</a>'
  apa: Coy, S., Czumaj, A., Feldmann, M., Hinnenthal, K., Kuhn, F., Scheideler, C.,
    Schneider, P., &#38; Struijs, M. (2021). Near-Shortest Path Routing in Hybrid
    Communication Networks. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th
    International Conference on Principles of Distributed Systems, OPODIS 2021, December
    13-15, 2021, Strasbourg, France</i> (Vol. 217, p. 11:1–11:23). Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">https://doi.org/10.4230/LIPIcs.OPODIS.2021.11</a>
  bibtex: '@inproceedings{Coy_Czumaj_Feldmann_Hinnenthal_Kuhn_Scheideler_Schneider_Struijs_2021,
    series={LIPIcs}, title={Near-Shortest Path Routing in Hybrid Communication Networks},
    volume={217}, DOI={<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">10.4230/LIPIcs.OPODIS.2021.11</a>},
    booktitle={25th International Conference on Principles of Distributed Systems,
    OPODIS 2021, December 13-15, 2021, Strasbourg, France}, publisher={Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik}, author={Coy, Sam and Czumaj, Artur and Feldmann,
    Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and
    Schneider, Philipp and Struijs, Martijn}, editor={Bramas, Quentin and Gramoli,
    Vincent and Milani, Alessia}, year={2021}, pages={11:1–11:23}, collection={LIPIcs}
    }'
  chicago: Coy, Sam, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn,
    Christian Scheideler, Philipp Schneider, and Martijn Struijs. “Near-Shortest Path
    Routing in Hybrid Communication Networks.” In <i>25th International Conference
    on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg,
    France</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, 217:11:1–11:23.
    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">https://doi.org/10.4230/LIPIcs.OPODIS.2021.11</a>.
  ieee: 'S. Coy <i>et al.</i>, “Near-Shortest Path Routing in Hybrid Communication
    Networks,” in <i>25th International Conference on Principles of Distributed Systems,
    OPODIS 2021, December 13-15, 2021, Strasbourg, France</i>, 2021, vol. 217, p.
    11:1–11:23, doi: <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">10.4230/LIPIcs.OPODIS.2021.11</a>.'
  mla: Coy, Sam, et al. “Near-Shortest Path Routing in Hybrid Communication Networks.”
    <i>25th International Conference on Principles of Distributed Systems, OPODIS
    2021, December 13-15, 2021, Strasbourg, France</i>, edited by Quentin Bramas et
    al., vol. 217, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 11:1–11:23,
    doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2021.11">10.4230/LIPIcs.OPODIS.2021.11</a>.
  short: 'S. Coy, A. Czumaj, M. Feldmann, K. Hinnenthal, F. Kuhn, C. Scheideler, P.
    Schneider, M. Struijs, in: Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International
    Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15,
    2021, Strasbourg, France, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021,
    p. 11:1–11:23.'
date_created: 2022-03-09T10:43:28Z
date_updated: 2022-03-09T10:46:34Z
department:
- _id: '79'
doi: 10.4230/LIPIcs.OPODIS.2021.11
editor:
- first_name: Quentin
  full_name: Bramas, Quentin
  last_name: Bramas
- first_name: Vincent
  full_name: Gramoli, Vincent
  last_name: Gramoli
- first_name: Alessia
  full_name: Milani, Alessia
  last_name: Milani
intvolume: '       217'
language:
- iso: eng
page: 11:1–11:23
publication: 25th International Conference on Principles of Distributed Systems, OPODIS
  2021, December 13-15, 2021, Strasbourg, France
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
series_title: LIPIcs
status: public
title: Near-Shortest Path Routing in Hybrid Communication Networks
type: conference
user_id: '15504'
volume: 217
year: '2021'
...
---
_id: '20221'
author:
- first_name: Paresh Kishor
  full_name: Yeole, Paresh Kishor
  last_name: Yeole
citation:
  ama: Yeole PK. <i>Plurality Consensus in Hybrid Networks</i>.; 2020.
  apa: Yeole, P. K. (2020). <i>Plurality Consensus in Hybrid Networks</i>.
  bibtex: '@book{Yeole_2020, title={Plurality Consensus in Hybrid Networks}, author={Yeole,
    Paresh Kishor}, year={2020} }'
  chicago: Yeole, Paresh Kishor. <i>Plurality Consensus in Hybrid Networks</i>, 2020.
  ieee: P. K. Yeole, <i>Plurality Consensus in Hybrid Networks</i>. 2020.
  mla: Yeole, Paresh Kishor. <i>Plurality Consensus in Hybrid Networks</i>. 2020.
  short: P.K. Yeole, Plurality Consensus in Hybrid Networks, 2020.
date_created: 2020-10-29T07:45:57Z
date_updated: 2022-01-06T06:54:23Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Plurality Consensus in Hybrid Networks
type: mastersthesis
user_id: '15504'
year: '2020'
...
---
_id: '17836'
citation:
  ama: Werneck Richa A, Scheideler C, eds. <i>Structural Information and Communication
    Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany,
    June 29 - July 1, 2020, Proceedings</i>. Vol 12156. Springer; 2020. doi:<a href="https://doi.org/10.1007/978-3-030-54921-3">10.1007/978-3-030-54921-3</a>
  apa: Werneck Richa, A., &#38; Scheideler, C. (Eds.). (2020). <i>Structural Information
    and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn,
    Germany, June 29 - July 1, 2020, Proceedings</i> (Vol. 12156). Springer. <a href="https://doi.org/10.1007/978-3-030-54921-3">https://doi.org/10.1007/978-3-030-54921-3</a>
  bibtex: '@book{Werneck Richa_Scheideler_2020, series={Lecture Notes in Computer
    Science}, title={Structural Information and Communication Complexity - 27th International
    Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings},
    volume={12156}, DOI={<a href="https://doi.org/10.1007/978-3-030-54921-3">10.1007/978-3-030-54921-3</a>},
    publisher={Springer}, year={2020}, collection={Lecture Notes in Computer Science}
    }'
  chicago: Werneck Richa, Andrea, and Christian Scheideler, eds. <i>Structural Information
    and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn,
    Germany, June 29 - July 1, 2020, Proceedings</i>. Vol. 12156. Lecture Notes in
    Computer Science. Springer, 2020. <a href="https://doi.org/10.1007/978-3-030-54921-3">https://doi.org/10.1007/978-3-030-54921-3</a>.
  ieee: A. Werneck Richa and C. Scheideler, Eds., <i>Structural Information and Communication
    Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany,
    June 29 - July 1, 2020, Proceedings</i>, vol. 12156. Springer, 2020.
  mla: Werneck Richa, Andrea, and Christian Scheideler, editors. <i>Structural Information
    and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn,
    Germany, June 29 - July 1, 2020, Proceedings</i>. Vol. 12156, Springer, 2020,
    doi:<a href="https://doi.org/10.1007/978-3-030-54921-3">10.1007/978-3-030-54921-3</a>.
  short: A. Werneck Richa, C. Scheideler, eds., Structural Information and Communication
    Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany,
    June 29 - July 1, 2020, Proceedings, Springer, 2020.
date_created: 2020-08-12T07:54:22Z
date_updated: 2022-01-06T06:53:20Z
department:
- _id: '79'
doi: 10.1007/978-3-030-54921-3
editor:
- first_name: Andrea
  full_name: Werneck Richa, Andrea
  last_name: Werneck Richa
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
intvolume: '     12156'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publication_identifier:
  isbn:
  - 978-3-030-54920-6
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Structural Information and Communication Complexity - 27th International Colloquium,
  SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings
type: conference_editor
user_id: '15504'
volume: 12156
year: '2020'
...
---
_id: '17839'
citation:
  ama: 'Scheideler C, Spear M, eds. <i>SPAA ’20: 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020</i>. ACM;
    2020. doi:<a href="https://doi.org/10.1145/3350755">10.1145/3350755</a>'
  apa: 'Scheideler, C., &#38; Spear, M. (Eds.). (2020). <i>SPAA ’20: 32nd ACM Symposium
    on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17,
    2020</i>. ACM. <a href="https://doi.org/10.1145/3350755">https://doi.org/10.1145/3350755</a>'
  bibtex: '@book{Scheideler_Spear_2020, title={SPAA ’20: 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020}, DOI={<a
    href="https://doi.org/10.1145/3350755">10.1145/3350755</a>}, publisher={ACM},
    year={2020} }'
  chicago: 'Scheideler, Christian, and Michael Spear, eds. <i>SPAA ’20: 32nd ACM Symposium
    on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17,
    2020</i>. ACM, 2020. <a href="https://doi.org/10.1145/3350755">https://doi.org/10.1145/3350755</a>.'
  ieee: 'C. Scheideler and M. Spear, Eds., <i>SPAA ’20: 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020</i>. ACM,
    2020.'
  mla: 'Scheideler, Christian, and Michael Spear, editors. <i>SPAA ’20: 32nd ACM Symposium
    on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17,
    2020</i>. ACM, 2020, doi:<a href="https://doi.org/10.1145/3350755">10.1145/3350755</a>.'
  short: 'C. Scheideler, M. Spear, eds., SPAA ’20: 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, ACM, 2020.'
date_created: 2020-08-12T07:57:10Z
date_updated: 2022-01-06T06:53:20Z
department:
- _id: '79'
doi: 10.1145/3350755
editor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Michael
  full_name: Spear, Michael
  last_name: Spear
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication_identifier:
  isbn:
  - 978-1-4503-6935-0
publisher: ACM
status: public
title: 'SPAA ''20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures,
  Virtual Event, USA, July 15-17, 2020'
type: conference_editor
user_id: '15504'
year: '2020'
...
---
_id: '20495'
author:
- first_name: Moritz
  full_name: Jochmaring, Moritz
  last_name: Jochmaring
citation:
  ama: Jochmaring M. <i>A Self Stabilizing Protocol for Well-Formed Trees in Hybrid
    Networks</i>.; 2020.
  apa: Jochmaring, M. (2020). <i>A self stabilizing protocol for well-formed trees
    in hybrid networks</i>.
  bibtex: '@book{Jochmaring_2020, title={A self stabilizing protocol for well-formed
    trees in hybrid networks}, author={Jochmaring, Moritz}, year={2020} }'
  chicago: Jochmaring, Moritz. <i>A Self Stabilizing Protocol for Well-Formed Trees
    in Hybrid Networks</i>, 2020.
  ieee: M. Jochmaring, <i>A self stabilizing protocol for well-formed trees in hybrid
    networks</i>. 2020.
  mla: Jochmaring, Moritz. <i>A Self Stabilizing Protocol for Well-Formed Trees in
    Hybrid Networks</i>. 2020.
  short: M. Jochmaring, A Self Stabilizing Protocol for Well-Formed Trees in Hybrid
    Networks, 2020.
date_created: 2020-11-25T07:03:16Z
date_updated: 2022-01-06T06:54:27Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: A self stabilizing protocol for well-formed trees in hybrid networks
type: mastersthesis
user_id: '15504'
year: '2020'
...
---
_id: '20755'
abstract:
- lang: eng
  text: "We consider the problem of computing shortest paths in \\emph{hybrid networks},
    in which nodes can make use of different communication modes. For example, mobile
    phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular
    network to solve tasks more efficiently. Like in this case, the different communication
    modes may differ considerably in range, bandwidth, and flexibility. We build upon
    the model of Augustine et al. [SODA '20], which captures these differences by
    a \\emph{local} and a \\emph{global} mode. Specifically, the local edges model
    a fixed communication network in which $O(1)$ messages of size $O(\\log n)$ can
    be sent over every edge in each synchronous round. The global edges form a clique,
    but nodes are only allowed to send and receive a total of at most $O(\\log n)$
    messages over global edges, which restricts the nodes to use these edges only
    very sparsely.\r\n\r\nWe demonstrate the power of hybrid networks by presenting
    algorithms to compute Single-Source Shortest Paths and the diameter very efficiently
    in \\emph{sparse graphs}. Specifically, we present exact $O(\\log n)$ time algorithms
    for cactus graphs (i.e., graphs in which each edge is contained in at most one
    cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges
    and arboricity $O(\\log n)$. For these graph classes, our algorithms provide exponentially
    faster solutions than the best known algorithms for general graphs in this model.\r\nBeyond
    shortest paths, we also provide a variety of useful tools and techniques for hybrid
    networks, which may be of independent interest.\r\n"
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
- first_name: Kristian
  full_name: Hinnenthal, Kristian
  id: '32229'
  last_name: Hinnenthal
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Feldmann M, Hinnenthal K, Scheideler C. Fast Hybrid Network Algorithms for
    Shortest Paths in Sparse Graphs. In: <i>Proceedings of the 24th International
    Conference on Principles of Distributed Systems (OPODIS)</i>. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2020.31">10.4230/LIPIcs.OPODIS.2020.31</a>'
  apa: Feldmann, M., Hinnenthal, K., &#38; Scheideler, C. (2020). Fast Hybrid Network
    Algorithms for Shortest Paths in Sparse Graphs. In <i>Proceedings of the 24th
    International Conference on Principles of Distributed Systems (OPODIS)</i>. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2020.31">https://doi.org/10.4230/LIPIcs.OPODIS.2020.31</a>
  bibtex: '@inproceedings{Feldmann_Hinnenthal_Scheideler_2020, title={Fast Hybrid
    Network Algorithms for Shortest Paths in Sparse Graphs}, DOI={<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2020.31">10.4230/LIPIcs.OPODIS.2020.31</a>},
    booktitle={Proceedings of the 24th International Conference on Principles of Distributed
    Systems (OPODIS)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
    author={Feldmann, Michael and Hinnenthal, Kristian and Scheideler, Christian},
    year={2020} }'
  chicago: Feldmann, Michael, Kristian Hinnenthal, and Christian Scheideler. “Fast
    Hybrid Network Algorithms for Shortest Paths in Sparse Graphs.” In <i>Proceedings
    of the 24th International Conference on Principles of Distributed Systems (OPODIS)</i>.
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2020.31">https://doi.org/10.4230/LIPIcs.OPODIS.2020.31</a>.
  ieee: M. Feldmann, K. Hinnenthal, and C. Scheideler, “Fast Hybrid Network Algorithms
    for Shortest Paths in Sparse Graphs,” in <i>Proceedings of the 24th International
    Conference on Principles of Distributed Systems (OPODIS)</i>, 2020.
  mla: Feldmann, Michael, et al. “Fast Hybrid Network Algorithms for Shortest Paths
    in Sparse Graphs.” <i>Proceedings of the 24th International Conference on Principles
    of Distributed Systems (OPODIS)</i>, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2020, doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2020.31">10.4230/LIPIcs.OPODIS.2020.31</a>.
  short: 'M. Feldmann, K. Hinnenthal, C. Scheideler, in: Proceedings of the 24th International
    Conference on Principles of Distributed Systems (OPODIS), Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2020.'
date_created: 2020-12-16T10:20:18Z
date_updated: 2022-01-06T06:54:36Z
ddc:
- '000'
department:
- _id: '79'
doi: 10.4230/LIPIcs.OPODIS.2020.31
external_id:
  arxiv:
  - '2007.01191'
file:
- access_level: closed
  content_type: application/pdf
  creator: mfeldma2
  date_created: 2020-12-16T10:18:50Z
  date_updated: 2020-12-16T10:18:50Z
  file_id: '20756'
  file_name: Fast_Hybrid_Network_Algorithms_for_Shortest_Paths_in_Sparse_Graphs.pdf
  file_size: 867373
  relation: main_file
  success: 1
file_date_updated: 2020-12-16T10:18:50Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '1'
  name: SFB 901
publication: Proceedings of the 24th International Conference on Principles of Distributed
  Systems (OPODIS)
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
status: public
title: Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs
type: conference
user_id: '23538'
year: '2020'
...
---
_id: '18066'
author:
- first_name: Michael
  full_name: Skowronek, Michael
  last_name: Skowronek
citation:
  ama: Skowronek M. <i>Approaches for Competetive Routing through Intersections of
    Hole Abstractions in Hybrid Communication Networks</i>. Universität Paderborn;
    2020.
  apa: Skowronek, M. (2020). <i>Approaches for Competetive Routing through Intersections
    of Hole Abstractions in Hybrid Communication Networks</i>. Universität Paderborn.
  bibtex: '@book{Skowronek_2020, title={Approaches for Competetive Routing through
    Intersections of Hole Abstractions in Hybrid Communication Networks}, publisher={Universität
    Paderborn}, author={Skowronek, Michael}, year={2020} }'
  chicago: Skowronek, Michael. <i>Approaches for Competetive Routing through Intersections
    of Hole Abstractions in Hybrid Communication Networks</i>. Universität Paderborn,
    2020.
  ieee: M. Skowronek, <i>Approaches for Competetive Routing through Intersections
    of Hole Abstractions in Hybrid Communication Networks</i>. Universität Paderborn,
    2020.
  mla: Skowronek, Michael. <i>Approaches for Competetive Routing through Intersections
    of Hole Abstractions in Hybrid Communication Networks</i>. Universität Paderborn,
    2020.
  short: M. Skowronek, Approaches for Competetive Routing through Intersections of
    Hole Abstractions in Hybrid Communication Networks, Universität Paderborn, 2020.
date_created: 2020-08-20T07:40:58Z
date_updated: 2022-01-06T06:53:25Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Approaches for Competetive Routing through Intersections of Hole Abstractions
  in Hybrid Communication Networks
type: bachelorsthesis
user_id: '477'
year: '2020'
...
---
_id: '18520'
author:
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: Setzer A. <i>Local Graph Transformation Primitives For Some Basic Problems
    In Overlay Networks</i>. Universität Paderborn; 2020. doi:<a href="https://doi.org/10.17619/UNIPB/1-1026">10.17619/UNIPB/1-1026</a>
  apa: Setzer, A. (2020). <i>Local Graph Transformation Primitives For Some Basic
    Problems In Overlay Networks</i>. Universität Paderborn. <a href="https://doi.org/10.17619/UNIPB/1-1026">https://doi.org/10.17619/UNIPB/1-1026</a>
  bibtex: '@book{Setzer_2020, title={Local Graph Transformation Primitives For Some
    Basic Problems In Overlay Networks}, DOI={<a href="https://doi.org/10.17619/UNIPB/1-1026">10.17619/UNIPB/1-1026</a>},
    publisher={Universität Paderborn}, author={Setzer, Alexander}, year={2020} }'
  chicago: Setzer, Alexander. <i>Local Graph Transformation Primitives For Some Basic
    Problems In Overlay Networks</i>. Universität Paderborn, 2020. <a href="https://doi.org/10.17619/UNIPB/1-1026">https://doi.org/10.17619/UNIPB/1-1026</a>.
  ieee: A. Setzer, <i>Local Graph Transformation Primitives For Some Basic Problems
    In Overlay Networks</i>. Universität Paderborn, 2020.
  mla: Setzer, Alexander. <i>Local Graph Transformation Primitives For Some Basic
    Problems In Overlay Networks</i>. Universität Paderborn, 2020, doi:<a href="https://doi.org/10.17619/UNIPB/1-1026">10.17619/UNIPB/1-1026</a>.
  short: A. Setzer, Local Graph Transformation Primitives For Some Basic Problems
    In Overlay Networks, Universität Paderborn, 2020.
date_created: 2020-08-28T06:50:29Z
date_updated: 2022-01-06T06:53:36Z
department:
- _id: '79'
doi: 10.17619/UNIPB/1-1026
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Local Graph Transformation Primitives For Some Basic Problems In Overlay Networks
type: dissertation
user_id: '477'
year: '2020'
...
---
_id: '18648'
author:
- first_name: Andreas
  full_name: Guggenmos, Andreas
  last_name: Guggenmos
citation:
  ama: Guggenmos A. <i>Algorithmen Für Selbststabilisierende Skip+-Delaunaygraphen</i>.
    Universität Paderborn; 2020.
  apa: Guggenmos, A. (2020). <i>Algorithmen für selbststabilisierende Skip+-Delaunaygraphen</i>.
    Universität Paderborn.
  bibtex: '@book{Guggenmos_2020, title={Algorithmen für selbststabilisierende Skip+-Delaunaygraphen},
    publisher={Universität Paderborn}, author={Guggenmos, Andreas}, year={2020} }'
  chicago: Guggenmos, Andreas. <i>Algorithmen Für Selbststabilisierende Skip+-Delaunaygraphen</i>.
    Universität Paderborn, 2020.
  ieee: A. Guggenmos, <i>Algorithmen für selbststabilisierende Skip+-Delaunaygraphen</i>.
    Universität Paderborn, 2020.
  mla: Guggenmos, Andreas. <i>Algorithmen Für Selbststabilisierende Skip+-Delaunaygraphen</i>.
    Universität Paderborn, 2020.
  short: A. Guggenmos, Algorithmen Für Selbststabilisierende Skip+-Delaunaygraphen,
    Universität Paderborn, 2020.
date_created: 2020-08-31T07:14:51Z
date_updated: 2022-01-06T06:53:50Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Algorithmen für selbststabilisierende Skip+-Delaunaygraphen
type: bachelorsthesis
user_id: '477'
year: '2020'
...
---
_id: '16902'
abstract:
- lang: eng
  text: "The maintenance of efficient and robust overlay networks is one\r\nof the
    most fundamental and reoccurring themes in networking.\r\nThis paper presents
    a survey of state-of-the-art \r\nalgorithms to design and repair overlay networks
    in a distributed\r\nmanner. In particular, we discuss basic algorithmic primitives\r\nto
    preserve connectivity, review algorithms for the fundamental\r\nproblem of graph
    linearization, and then survey self-stabilizing\r\nalgorithms for metric and scalable
    topologies. \r\nWe also identify open problems and avenues for future research.\r\n"
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
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: Feldmann M, Scheideler C, Schmid S. Survey on Algorithms for Self-Stabilizing
    Overlay Networks. <i>ACM Computing Surveys</i>. 2020. doi:<a href="https://doi.org/10.1145/3397190">10.1145/3397190</a>
  apa: Feldmann, M., Scheideler, C., &#38; Schmid, S. (2020). Survey on Algorithms
    for Self-Stabilizing Overlay Networks. <i>ACM Computing Surveys</i>. <a href="https://doi.org/10.1145/3397190">https://doi.org/10.1145/3397190</a>
  bibtex: '@article{Feldmann_Scheideler_Schmid_2020, title={Survey on Algorithms for
    Self-Stabilizing Overlay Networks}, DOI={<a href="https://doi.org/10.1145/3397190">10.1145/3397190</a>},
    journal={ACM Computing Surveys}, publisher={ACM}, author={Feldmann, Michael and
    Scheideler, Christian and Schmid, Stefan}, year={2020} }'
  chicago: Feldmann, Michael, Christian Scheideler, and Stefan Schmid. “Survey on
    Algorithms for Self-Stabilizing Overlay Networks.” <i>ACM Computing Surveys</i>,
    2020. <a href="https://doi.org/10.1145/3397190">https://doi.org/10.1145/3397190</a>.
  ieee: M. Feldmann, C. Scheideler, and S. Schmid, “Survey on Algorithms for Self-Stabilizing
    Overlay Networks,” <i>ACM Computing Surveys</i>, 2020.
  mla: Feldmann, Michael, et al. “Survey on Algorithms for Self-Stabilizing Overlay
    Networks.” <i>ACM Computing Surveys</i>, ACM, 2020, doi:<a href="https://doi.org/10.1145/3397190">10.1145/3397190</a>.
  short: M. Feldmann, C. Scheideler, S. Schmid, ACM Computing Surveys (2020).
date_created: 2020-04-29T07:09:50Z
date_updated: 2022-01-06T06:52:58Z
department:
- _id: '79'
doi: 10.1145/3397190
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: ACM Computing Surveys
publisher: ACM
status: public
title: Survey on Algorithms for Self-Stabilizing Overlay Networks
type: journal_article
user_id: '23538'
year: '2020'
...
---
_id: '16903'
abstract:
- lang: eng
  text: "We consider the clock synchronization problem in the (discrete) beeping model:
    Given a network of $n$ nodes with each node having a clock value $\\delta(v) \\in
    \\{0,\\ldots T-1\\}$, the goal is to synchronize the clock values of all nodes
    such that they have the same value in any round.\r\nAs is standard in clock synchronization,
    we assume \\emph{arbitrary activations} for all nodes, i.e., the nodes start their
    protocol at an arbitrary round (not limited to $\\{0,\\ldots,T-1\\}$).\r\nWe give
    an asymptotically optimal algorithm that runs in $4D + \\Bigl\\lfloor \\frac{D}{\\lfloor
    T/4 \\rfloor} \\Bigr \\rfloor \\cdot (T \\mod 4) = O(D)$ rounds, where $D$ is
    the diameter of the network.\r\nOnce all nodes are in sync, they beep at the same
    round every $T$ rounds.\r\nThe algorithm drastically improves on the $O(T D)$-bound
    of \\cite{firefly_sync} (where $T$ is required to be at least $4n$, so the bound
    is no better than $O(nD)$).\r\nOur algorithm is very simple as nodes only have
    to maintain $3$ bits in addition to the $\\lceil \\log T \\rceil$ bits needed
    to maintain the clock.\r\nFurthermore we investigate the complexity of \\emph{self-stabilizing}
    solutions for the clock synchronization problem: We first show lower bounds of
    $\\Omega(\\max\\{T,n\\})$ rounds on the runtime and $\\Omega(\\log(\\max\\{T,n\\}))$
    bits of memory required for any such protocol.\r\nAfterwards we present a protocol
    that runs in $O(\\max\\{T,n\\})$ rounds using at most $O(\\log(\\max\\{T,n\\}))$
    bits at each node, which is asymptotically optimal with regards to both, runtime
    and memory requirements."
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
- first_name: Ardalan
  full_name: Khazraei, Ardalan
  last_name: Khazraei
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Feldmann M, Khazraei A, Scheideler C. Time- and Space-Optimal Discrete Clock
    Synchronization in the Beeping Model. In: <i>Proceedings of the 32nd ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA)</i>. ACM; 2020. doi:<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>'
  apa: Feldmann, M., Khazraei, A., &#38; Scheideler, C. (2020). Time- and Space-Optimal
    Discrete Clock Synchronization in the Beeping Model. In <i>Proceedings of the
    32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>.
    ACM. <a href="https://doi.org/10.1145/3350755.3400246">https://doi.org/10.1145/3350755.3400246</a>
  bibtex: '@inproceedings{Feldmann_Khazraei_Scheideler_2020, title={Time- and Space-Optimal
    Discrete Clock Synchronization in the Beeping Model}, DOI={<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>},
    booktitle={Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, publisher={ACM}, author={Feldmann, Michael and Khazraei,
    Ardalan and Scheideler, Christian}, year={2020} }'
  chicago: Feldmann, Michael, Ardalan Khazraei, and Christian Scheideler. “Time- and
    Space-Optimal Discrete Clock Synchronization in the Beeping Model.” In <i>Proceedings
    of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>.
    ACM, 2020. <a href="https://doi.org/10.1145/3350755.3400246">https://doi.org/10.1145/3350755.3400246</a>.
  ieee: M. Feldmann, A. Khazraei, and C. Scheideler, “Time- and Space-Optimal Discrete
    Clock Synchronization in the Beeping Model,” in <i>Proceedings of the 32nd ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2020.
  mla: Feldmann, Michael, et al. “Time- and Space-Optimal Discrete Clock Synchronization
    in the Beeping Model.” <i>Proceedings of the 32nd ACM Symposium on Parallelism
    in Algorithms and Architectures (SPAA)</i>, ACM, 2020, doi:<a href="https://doi.org/10.1145/3350755.3400246">10.1145/3350755.3400246</a>.
  short: 'M. Feldmann, A. Khazraei, C. Scheideler, in: Proceedings of the 32nd ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM, 2020.'
date_created: 2020-04-29T07:16:35Z
date_updated: 2022-01-06T06:52:58Z
department:
- _id: '79'
doi: 10.1145/3350755.3400246
external_id:
  arxiv:
  - '2005.07388'
language:
- iso: eng
project:
- _id: '96'
  name: Algorithmen für programmierbare Materie in einem physiologischen Medium
publication: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
publisher: ACM
status: public
title: Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model
type: conference
user_id: '23538'
year: '2020'
...
---
_id: '15770'
author:
- first_name: Daniel
  full_name: Warner, Daniel
  last_name: Warner
citation:
  ama: Warner D. <i>On the Complexity of Local Transformations in SDN Overlays</i>.
    Universität Paderborn; 2020.
  apa: Warner, D. (2020). <i>On the complexity of local transformations in SDN overlays</i>.
    Universität Paderborn.
  bibtex: '@book{Warner_2020, title={On the complexity of local transformations in
    SDN overlays}, publisher={Universität Paderborn}, author={Warner, Daniel}, year={2020}
    }'
  chicago: Warner, Daniel. <i>On the Complexity of Local Transformations in SDN Overlays</i>.
    Universität Paderborn, 2020.
  ieee: D. Warner, <i>On the complexity of local transformations in SDN overlays</i>.
    Universität Paderborn, 2020.
  mla: Warner, Daniel. <i>On the Complexity of Local Transformations in SDN Overlays</i>.
    Universität Paderborn, 2020.
  short: D. Warner, On the Complexity of Local Transformations in SDN Overlays, Universität
    Paderborn, 2020.
date_created: 2020-02-04T13:47:02Z
date_updated: 2022-01-06T06:52:32Z
department:
- _id: '79'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '13'
  name: SFB 901 - Subproject C1
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: On the complexity of local transformations in SDN overlays
type: mastersthesis
user_id: '477'
year: '2020'
...