---
_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'
...
---
_id: '15169'
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Christina
  full_name: Kolb, Christina
  id: '43647'
  last_name: Kolb
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Castenow J, Kolb C, Scheideler C. A Bounding Box Overlay for Competitive Routing
    in Hybrid Communication Networks. In: <i>Proceedings of the 21st International
    Conference on Distributed Computing and Networking (ICDCN)</i>. ACM.'
  apa: 'Castenow, J., Kolb, C., &#38; Scheideler, C. (n.d.). A Bounding Box Overlay
    for Competitive Routing in Hybrid Communication Networks. In <i>Proceedings of
    the 21st International Conference on Distributed Computing and Networking (ICDCN)</i>.
    Kolkata, Indien: ACM.'
  bibtex: '@inproceedings{Castenow_Kolb_Scheideler, title={A Bounding Box Overlay
    for Competitive Routing in Hybrid Communication Networks}, booktitle={Proceedings
    of the 21st International Conference on Distributed Computing and Networking (ICDCN)},
    publisher={ACM}, author={Castenow, Jannik and Kolb, Christina and Scheideler,
    Christian} }'
  chicago: Castenow, Jannik, Christina Kolb, and Christian Scheideler. “A Bounding
    Box Overlay for Competitive Routing in Hybrid Communication Networks.” In <i>Proceedings
    of the 21st International Conference on Distributed Computing and Networking (ICDCN)</i>.
    ACM, n.d.
  ieee: J. Castenow, C. Kolb, and C. Scheideler, “A Bounding Box Overlay for Competitive
    Routing in Hybrid Communication Networks,” in <i>Proceedings of the 21st International
    Conference on Distributed Computing and Networking (ICDCN)</i>, Kolkata, Indien.
  mla: Castenow, Jannik, et al. “A Bounding Box Overlay for Competitive Routing in
    Hybrid Communication Networks.” <i>Proceedings of the 21st International Conference
    on Distributed Computing and Networking (ICDCN)</i>, ACM.
  short: 'J. Castenow, C. Kolb, C. Scheideler, in: Proceedings of the 21st International
    Conference on Distributed Computing and Networking (ICDCN), ACM, n.d.'
conference:
  end_date: 07.01.2020
  location: Kolkata, Indien
  name: '21st International Conference on Distributed Computing and Networking '
  start_date: 04.01.2020
date_created: 2019-11-25T12:18:41Z
date_updated: 2022-01-06T06:52:16Z
department:
- _id: '63'
- _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
publication: Proceedings of the 21st International Conference on Distributed Computing
  and Networking (ICDCN)
publication_status: accepted
publisher: ACM
status: public
title: A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '477'
year: '2020'
...
---
_id: '17809'
author:
- first_name: N.
  full_name: N., N.
  last_name: N.
citation:
  ama: N. N. <i>Scalable Multi Objective Path Optimization for Multi-Laser Selective
    Laser Melting Scanning Systems</i>.; 2019.
  apa: N., N. (2019). <i>Scalable Multi Objective Path Optimization for Multi-Laser
    Selective Laser Melting Scanning Systems</i>.
  bibtex: '@book{N._2019, title={Scalable Multi Objective Path Optimization for Multi-Laser
    Selective Laser Melting Scanning Systems}, author={N., N.}, year={2019} }'
  chicago: N., N. <i>Scalable Multi Objective Path Optimization for Multi-Laser Selective
    Laser Melting Scanning Systems</i>, 2019.
  ieee: N. N., <i>Scalable Multi Objective Path Optimization for Multi-Laser Selective
    Laser Melting Scanning Systems</i>. 2019.
  mla: N., N. <i>Scalable Multi Objective Path Optimization for Multi-Laser Selective
    Laser Melting Scanning Systems</i>. 2019.
  short: N. N., Scalable Multi Objective Path Optimization for Multi-Laser Selective
    Laser Melting Scanning Systems, 2019.
date_created: 2020-08-11T11:06:28Z
date_updated: 2022-01-06T06:53:20Z
department:
- _id: '79'
language:
- iso: eng
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Scalable Multi Objective Path Optimization for Multi-Laser Selective Laser
  Melting Scanning Systems
type: mastersthesis
user_id: '15504'
year: '2019'
...
---
_id: '8534'
abstract:
- lang: eng
  text: "We propose two protocols for distributed priority queues (denoted by 'heap'
    for simplicity in this paper) called SKEAP and SEAP. SKEAP realizes a distributed
    heap for a constant amount of priorities and SEAP one for an arbitrary amount.
    Both protocols build on an overlay, which induces an aggregation tree on which
    heap operations are aggregated in batches, ensuring that our protocols scale even
    for a high rate of incoming requests. As part of SEAP we provide a novel distributed
    protocol for the k-selection problem that runs in time O(log n) w.h.p. SKEAP guarantees
    sequential consistency for its heap operations, while SEAP guarantees serializability.
    SKEAP and SEAP provide logarithmic runtimes w.h.p. on all their operations. \r\nSKEAP
    and SEAP provide logarithmic runtimes w.h.p. on all their operations with SEAP
    having to use only O(log n) bit messages."
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. Skeap &#38; Seap: Scalable Distributed Priority
    Queues for Constant and Arbitrary Priorities. In: <i>Proceedings of the 31st ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ACM; 2019:287--296.
    doi:<a href="https://doi.org/10.1145/3323165.3323193">10.1145/3323165.3323193</a>'
  apa: 'Feldmann, M., &#38; Scheideler, C. (2019). Skeap &#38; Seap: Scalable Distributed
    Priority Queues for Constant and Arbitrary Priorities. In <i>Proceedings of the
    31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i> (pp.
    287--296). ACM. <a href="https://doi.org/10.1145/3323165.3323193">https://doi.org/10.1145/3323165.3323193</a>'
  bibtex: '@inproceedings{Feldmann_Scheideler_2019, title={Skeap &#38; Seap: Scalable
    Distributed Priority Queues for Constant and Arbitrary Priorities}, DOI={<a href="https://doi.org/10.1145/3323165.3323193">10.1145/3323165.3323193</a>},
    booktitle={Proceedings of the 31st ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, publisher={ACM}, author={Feldmann, Michael and Scheideler,
    Christian}, year={2019}, pages={287--296} }'
  chicago: 'Feldmann, Michael, and Christian Scheideler. “Skeap &#38; Seap: Scalable
    Distributed Priority Queues for Constant and Arbitrary Priorities.” In <i>Proceedings
    of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>,
    287--296. ACM, 2019. <a href="https://doi.org/10.1145/3323165.3323193">https://doi.org/10.1145/3323165.3323193</a>.'
  ieee: 'M. Feldmann and C. Scheideler, “Skeap &#38; Seap: Scalable Distributed Priority
    Queues for Constant and Arbitrary Priorities,” in <i>Proceedings of the 31st ACM
    Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, 2019, pp.
    287--296.'
  mla: 'Feldmann, Michael, and Christian Scheideler. “Skeap &#38; Seap: Scalable Distributed
    Priority Queues for Constant and Arbitrary Priorities.” <i>Proceedings of the
    31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>,
    ACM, 2019, pp. 287--296, doi:<a href="https://doi.org/10.1145/3323165.3323193">10.1145/3323165.3323193</a>.'
  short: 'M. Feldmann, C. Scheideler, in: Proceedings of the 31st ACM Symposium on
    Parallelism in Algorithms and Architectures (SPAA), ACM, 2019, pp. 287--296.'
date_created: 2019-03-21T14:37:26Z
date_updated: 2022-01-06T07:03:56Z
ddc:
- '004'
department:
- _id: '79'
doi: 10.1145/3323165.3323193
external_id:
  arxiv:
  - '1805.03472'
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2019-08-26T09:14:32Z
  date_updated: 2019-08-26T09:14:32Z
  file_id: '12954'
  file_name: p287-feldmann.pdf
  file_size: 1295095
  relation: main_file
  success: 1
file_date_updated: 2019-08-26T09:14:32Z
has_accepted_license: '1'
language:
- iso: eng
page: 287--296
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
publisher: ACM
status: public
title: 'Skeap & Seap: Scalable Distributed Priority Queues for Constant and Arbitrary
  Priorities'
type: conference
user_id: '477'
year: '2019'
...
---
_id: '8871'
author:
- first_name: John
  full_name: Augustine, John
  last_name: Augustine
- first_name: Mohsen
  full_name: Ghaffari, Mohsen
  last_name: Ghaffari
- first_name: Robert
  full_name: Gmyr, Robert
  last_name: Gmyr
- first_name: Kristian
  full_name: Hinnenthal, Kristian
  id: '32229'
  last_name: Hinnenthal
- first_name: Fabian
  full_name: Kuhn, Fabian
  last_name: Kuhn
- first_name: Jason
  full_name: Li, Jason
  last_name: Li
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Augustine J, Ghaffari M, Gmyr R, et al. Distributed Computation in Node-Capacitated
    Networks. In: <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms
    and Architectures</i>. ACM; 2019:69--79. doi:<a href="https://doi.org/10.1145/3323165.3323195">10.1145/3323165.3323195</a>'
  apa: Augustine, J., Ghaffari, M., Gmyr, R., Hinnenthal, K., Kuhn, F., Li, J., &#38;
    Scheideler, C. (2019). Distributed Computation in Node-Capacitated Networks. In
    <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures</i>
    (pp. 69--79). ACM. <a href="https://doi.org/10.1145/3323165.3323195">https://doi.org/10.1145/3323165.3323195</a>
  bibtex: '@inproceedings{Augustine_Ghaffari_Gmyr_Hinnenthal_Kuhn_Li_Scheideler_2019,
    title={Distributed Computation in Node-Capacitated Networks}, DOI={<a href="https://doi.org/10.1145/3323165.3323195">10.1145/3323165.3323195</a>},
    booktitle={Proceedings of the 31st ACM Symposium on Parallelism in Algorithms
    and Architectures}, publisher={ACM}, author={Augustine, John and Ghaffari, Mohsen
    and Gmyr, Robert and Hinnenthal, Kristian and Kuhn, Fabian and Li, Jason and Scheideler,
    Christian}, year={2019}, pages={69--79} }'
  chicago: Augustine, John, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian
    Kuhn, Jason Li, and Christian Scheideler. “Distributed Computation in Node-Capacitated
    Networks.” In <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms
    and Architectures</i>, 69--79. ACM, 2019. <a href="https://doi.org/10.1145/3323165.3323195">https://doi.org/10.1145/3323165.3323195</a>.
  ieee: J. Augustine <i>et al.</i>, “Distributed Computation in Node-Capacitated Networks,”
    in <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    2019, pp. 69--79.
  mla: Augustine, John, et al. “Distributed Computation in Node-Capacitated Networks.”
    <i>Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures</i>,
    ACM, 2019, pp. 69--79, doi:<a href="https://doi.org/10.1145/3323165.3323195">10.1145/3323165.3323195</a>.
  short: 'J. Augustine, M. Ghaffari, R. Gmyr, K. Hinnenthal, F. Kuhn, J. Li, C. Scheideler,
    in: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures,
    ACM, 2019, pp. 69--79.'
date_created: 2019-04-10T08:20:34Z
date_updated: 2022-01-06T07:04:04Z
ddc:
- '004'
department:
- _id: '79'
doi: 10.1145/3323165.3323195
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2019-08-26T11:17:58Z
  date_updated: 2019-08-26T11:17:58Z
  file_id: '12964'
  file_name: p69-augustine.pdf
  file_size: 1275192
  relation: main_file
  success: 1
file_date_updated: 2019-08-26T11:17:58Z
has_accepted_license: '1'
language:
- iso: eng
page: 69--79
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and
  Architectures
publisher: ACM
status: public
title: Distributed Computation in Node-Capacitated Networks
type: conference
user_id: '477'
year: '2019'
...
---
_id: '6976'
abstract:
- lang: eng
  text: "We investigate the maintenance of overlay networks under massive churn, i.e.\r\nnodes
    joining and leaving the network. We assume an adversary that may churn a\r\nconstant
    fraction $\\alpha n$ of nodes over the course of $\\mathcal{O}(\\log n)$\r\nrounds.
    In particular, the adversary has an almost up-to-date information of\r\nthe network
    topology as it can observe an only slightly outdated topology that\r\nis at least
    $2$ rounds old. Other than that, we only have the provably minimal\r\nrestriction
    that new nodes can only join the network via nodes that have taken\r\npart in
    the network for at least one round.\r\n  Our contributions are as follows: First,
    we show that it is impossible to\r\nmaintain a connected topology if adversary
    has up-to-date information about the\r\nnodes' connections. Further, we show that
    our restriction concerning the join\r\nis also necessary. As our main result present
    an algorithm that constructs a\r\nnew overlay- completely independent of all previous
    overlays - every $2$\r\nrounds. Furthermore, each node sends and receives only
    $\\mathcal{O}(\\log^3 n)$\r\nmessages each round. As part of our solution we propose
    the Linearized DeBruijn\r\nSwarm (LDS), a highly churn resistant overlay, which
    will be maintained by the\r\nalgorithm. However, our approaches can be transferred
    to a variety of classical\r\nP2P Topologies where nodes are mapped into the $[0,1)$-interval."
author:
- first_name: Thorsten
  full_name: Götte, Thorsten
  id: '34727'
  last_name: Götte
- first_name: Vipin Ravindran
  full_name: Vijayalakshmi, Vipin Ravindran
  last_name: Vijayalakshmi
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Götte T, Vijayalakshmi VR, Scheideler C. Always be Two Steps Ahead of Your
    Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date
    Adversary. In: <i>Proceedings of the 2019 IEEE 33rd International Parallel  and
    Distributed Processing Symposium (IPDPS ’19)</i>. IEEE.'
  apa: 'Götte, T., Vijayalakshmi, V. R., &#38; Scheideler, C. (n.d.). Always be Two
    Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn
    with an Almost Up-to-date Adversary. In <i>Proceedings of the 2019 IEEE 33rd International
    Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>. Rio de Janeiro,
    Brazil: IEEE.'
  bibtex: '@inproceedings{Götte_Vijayalakshmi_Scheideler, title={Always be Two Steps
    Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with
    an Almost Up-to-date Adversary}, booktitle={Proceedings of the 2019 IEEE 33rd
    International Parallel  and Distributed Processing Symposium (IPDPS ’19)}, publisher={IEEE},
    author={Götte, Thorsten and Vijayalakshmi, Vipin Ravindran and Scheideler, Christian}
    }'
  chicago: Götte, Thorsten, Vipin Ravindran Vijayalakshmi, and Christian Scheideler.
    “Always Be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under
    Massive Churn with an Almost Up-to-Date Adversary.” In <i>Proceedings of the 2019
    IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS
    ’19)</i>. IEEE, n.d.
  ieee: T. Götte, V. R. Vijayalakshmi, and C. Scheideler, “Always be Two Steps Ahead
    of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost
    Up-to-date Adversary,” in <i>Proceedings of the 2019 IEEE 33rd International Parallel 
    and Distributed Processing Symposium (IPDPS ’19)</i>, Rio de Janeiro, Brazil.
  mla: Götte, Thorsten, et al. “Always Be Two Steps Ahead of Your Enemy - Maintaining
    a Routable Overlay under Massive Churn with an Almost Up-to-Date Adversary.” <i>Proceedings
    of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium
    (IPDPS ’19)</i>, IEEE.
  short: 'T. Götte, V.R. Vijayalakshmi, C. Scheideler, in: Proceedings of the 2019
    IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS
    ’19), IEEE, n.d.'
conference:
  end_date: 24.05.19
  location: Rio de Janeiro, Brazil
  name: 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium
    (IPDPS '19)
  start_date: 20.05.19
date_created: 2019-01-24T18:53:11Z
date_updated: 2022-01-06T07:03:25Z
ddc:
- '000'
department:
- _id: '79'
file:
- access_level: closed
  content_type: application/pdf
  creator: thgoette
  date_created: 2019-01-26T16:09:08Z
  date_updated: 2019-01-26T16:09:08Z
  file_id: '7007'
  file_name: Always_be_Two_Steps_Ahead_of_Your_Enemy.pdf
  file_size: 638020
  relation: main_file
  success: 1
file_date_updated: 2019-01-26T16:09:08Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
publication: Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed
  Processing Symposium (IPDPS '19)
publication_status: accepted
publisher: IEEE
status: public
title: Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under
  Massive Churn with an Almost Up-to-date Adversary
type: conference
user_id: '34727'
year: '2019'
...
---
_id: '10586'
abstract:
- lang: eng
  text: We consider the problem of transforming a given graph G_s into a desired graph
    G_t by applying a minimum number of primitives from a particular set of local
    graph transformation primitives. These primitives are local in the sense that
    each node can apply them based on local knowledge and by affecting only its 1-neighborhood.
    Although the specific set of primitives we consider makes it possible to transform
    any (weakly) connected graph into any other (weakly) connected graph consisting
    of the same nodes, they cannot disconnect the graph or introduce new nodes into
    the graph, making them ideal in the context of supervised overlay network transformations.
    We prove that computing a minimum sequence of primitive applications (even centralized)
    for arbitrary G_s and G_t is NP-hard, which we conjecture to hold for any set
    of local graph transformation primitives satisfying the aforementioned properties.
    On the other hand, we show that this problem admits a polynomial time algorithm
    with a constant approximation ratio.
author:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Scheideler C, Setzer A. On the Complexity of Local Graph Transformations.
    In: <i>Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming</i>. Vol 132. LIPIcs. Dagstuhl Publishing; 2019:150:1--150:14.
    doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>'
  apa: 'Scheideler, C., &#38; Setzer, A. (2019). On the Complexity of Local Graph
    Transformations. In <i>Proceedings of the 46th International Colloquium on Automata,
    Languages, and Programming</i> (Vol. 132, pp. 150:1--150:14). Patras, Greece:
    Dagstuhl Publishing. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>'
  bibtex: '@inproceedings{Scheideler_Setzer_2019, series={LIPIcs}, title={On the Complexity
    of Local Graph Transformations}, volume={132}, DOI={<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>},
    booktitle={Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming}, publisher={Dagstuhl Publishing}, author={Scheideler, Christian
    and Setzer, Alexander}, year={2019}, pages={150:1--150:14}, collection={LIPIcs}
    }'
  chicago: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local
    Graph Transformations.” In <i>Proceedings of the 46th International Colloquium
    on Automata, Languages, and Programming</i>, 132:150:1--150:14. LIPIcs. Dagstuhl
    Publishing, 2019. <a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">https://doi.org/10.4230/LIPICS.ICALP.2019.150</a>.
  ieee: C. Scheideler and A. Setzer, “On the Complexity of Local Graph Transformations,”
    in <i>Proceedings of the 46th International Colloquium on Automata, Languages,
    and Programming</i>, Patras, Greece, 2019, vol. 132, pp. 150:1--150:14.
  mla: Scheideler, Christian, and Alexander Setzer. “On the Complexity of Local Graph
    Transformations.” <i>Proceedings of the 46th International Colloquium on Automata,
    Languages, and Programming</i>, vol. 132, Dagstuhl Publishing, 2019, pp. 150:1--150:14,
    doi:<a href="https://doi.org/10.4230/LIPICS.ICALP.2019.150">10.4230/LIPICS.ICALP.2019.150</a>.
  short: 'C. Scheideler, A. Setzer, in: Proceedings of the 46th International Colloquium
    on Automata, Languages, and Programming, Dagstuhl Publishing, 2019, pp. 150:1--150:14.'
conference:
  end_date: 2019-07-12
  location: Patras, Greece
  name: ICALP 2019
  start_date: 2019-07-09
date_created: 2019-07-08T17:19:01Z
date_updated: 2022-01-06T06:50:45Z
ddc:
- '004'
department:
- _id: '79'
doi: 10.4230/LIPICS.ICALP.2019.150
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2019-08-26T09:21:27Z
  date_updated: 2019-08-26T09:21:27Z
  file_id: '12955'
  file_name: LIPIcs-ICALP-2019-150.pdf
  file_size: 537649
  relation: main_file
  success: 1
file_date_updated: 2019-08-26T09:21:27Z
has_accepted_license: '1'
intvolume: '       132'
keyword:
- Graphs transformations
- NP-hardness
- approximation algorithms
language:
- iso: eng
page: 150:1--150:14
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 46th International Colloquium on Automata, Languages,
  and Programming
publication_status: published
publisher: Dagstuhl Publishing
series_title: LIPIcs
status: public
title: On the Complexity of Local Graph Transformations
type: conference
user_id: '477'
volume: 132
year: '2019'
...
---
_id: '14829'
citation:
  ama: Scheideler C, Berenbrink P, eds. <i>The 31st ACM Symposium on Parallelism in
    Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019</i>.
    ACM; 2019. doi:<a href="https://doi.org/10.1145/3323165">10.1145/3323165</a>
  apa: Scheideler, C., &#38; Berenbrink, P. (Eds.). (2019). <i>The 31st ACM Symposium
    on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June
    22-24, 2019</i>. ACM. <a href="https://doi.org/10.1145/3323165">https://doi.org/10.1145/3323165</a>
  bibtex: '@book{Scheideler_Berenbrink_2019, title={The 31st ACM Symposium on Parallelism
    in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019},
    DOI={<a href="https://doi.org/10.1145/3323165">10.1145/3323165</a>}, publisher={ACM},
    year={2019} }'
  chicago: Scheideler, Christian, and Petra Berenbrink, eds. <i>The 31st ACM Symposium
    on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June
    22-24, 2019</i>. ACM, 2019. <a href="https://doi.org/10.1145/3323165">https://doi.org/10.1145/3323165</a>.
  ieee: C. Scheideler and P. Berenbrink, Eds., <i>The 31st ACM Symposium on Parallelism
    in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019</i>.
    ACM, 2019.
  mla: Scheideler, Christian, and Petra Berenbrink, editors. <i>The 31st ACM Symposium
    on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June
    22-24, 2019</i>. ACM, 2019, doi:<a href="https://doi.org/10.1145/3323165">10.1145/3323165</a>.
  short: C. Scheideler, P. Berenbrink, eds., The 31st ACM Symposium on Parallelism
    in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019,
    ACM, 2019.
date_created: 2019-11-06T10:43:41Z
date_updated: 2022-01-06T06:52:07Z
department:
- _id: '79'
doi: 10.1145/3323165
editor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Petra
  full_name: Berenbrink, Petra
  last_name: Berenbrink
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-6184-2
publisher: ACM
status: public
title: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA
  2019, Phoenix, AZ, USA, June 22-24, 2019
type: conference_editor
user_id: '477'
year: '2019'
...
---
_id: '14830'
author:
- first_name: Robert
  full_name: Gmyr, Robert
  last_name: Gmyr
- first_name: Jonas
  full_name: Lefevre, Jonas
  last_name: Lefevre
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: Gmyr R, Lefevre J, Scheideler C. Self-Stabilizing Metric Graphs. <i>Theory
    Comput Syst</i>. 2019;63(2):177-199. doi:<a href="https://doi.org/10.1007/s00224-017-9823-4">10.1007/s00224-017-9823-4</a>
  apa: Gmyr, R., Lefevre, J., &#38; Scheideler, C. (2019). Self-Stabilizing Metric
    Graphs. <i>Theory Comput. Syst.</i>, <i>63</i>(2), 177–199. <a href="https://doi.org/10.1007/s00224-017-9823-4">https://doi.org/10.1007/s00224-017-9823-4</a>
  bibtex: '@article{Gmyr_Lefevre_Scheideler_2019, title={Self-Stabilizing Metric Graphs},
    volume={63}, DOI={<a href="https://doi.org/10.1007/s00224-017-9823-4">10.1007/s00224-017-9823-4</a>},
    number={2}, journal={Theory Comput. Syst.}, author={Gmyr, Robert and Lefevre,
    Jonas and Scheideler, Christian}, year={2019}, pages={177–199} }'
  chicago: 'Gmyr, Robert, Jonas Lefevre, and Christian Scheideler. “Self-Stabilizing
    Metric Graphs.” <i>Theory Comput. Syst.</i> 63, no. 2 (2019): 177–99. <a href="https://doi.org/10.1007/s00224-017-9823-4">https://doi.org/10.1007/s00224-017-9823-4</a>.'
  ieee: R. Gmyr, J. Lefevre, and C. Scheideler, “Self-Stabilizing Metric Graphs,”
    <i>Theory Comput. Syst.</i>, vol. 63, no. 2, pp. 177–199, 2019.
  mla: Gmyr, Robert, et al. “Self-Stabilizing Metric Graphs.” <i>Theory Comput. Syst.</i>,
    vol. 63, no. 2, 2019, pp. 177–99, doi:<a href="https://doi.org/10.1007/s00224-017-9823-4">10.1007/s00224-017-9823-4</a>.
  short: R. Gmyr, J. Lefevre, C. Scheideler, Theory Comput. Syst. 63 (2019) 177–199.
date_created: 2019-11-06T10:54:58Z
date_updated: 2022-01-06T06:52:07Z
department:
- _id: '79'
doi: 10.1007/s00224-017-9823-4
intvolume: '        63'
issue: '2'
language:
- iso: eng
page: 177-199
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
publication: Theory Comput. Syst.
status: public
title: Self-Stabilizing Metric Graphs
type: journal_article
user_id: '15504'
volume: 63
year: '2019'
...
---
_id: '14539'
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Christina
  full_name: Kolb, Christina
  id: '43647'
  last_name: Kolb
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Castenow J, Kolb C, Scheideler C. A Bounding Box Overlay for Competitive Routing
    in Hybrid Communication Networks. In: <i>Proceedings of the 26th International
    Colloquium on Structural Information and Communication Complexity (SIROCCO)</i>.
    ; 2019:345-348. doi:<a href="https://doi.org/10.1007/978-3-030-24922-9\_26">10.1007/978-3-030-24922-9\_26</a>'
  apa: Castenow, J., Kolb, C., &#38; Scheideler, C. (2019). A Bounding Box Overlay
    for Competitive Routing in Hybrid Communication Networks. In <i>Proceedings of
    the 26th International Colloquium on Structural Information and Communication
    Complexity (SIROCCO)</i> (pp. 345–348). L’Aquila, Italy. <a href="https://doi.org/10.1007/978-3-030-24922-9\_26">https://doi.org/10.1007/978-3-030-24922-9\_26</a>
  bibtex: '@inproceedings{Castenow_Kolb_Scheideler_2019, title={A Bounding Box Overlay
    for Competitive Routing in Hybrid Communication Networks}, DOI={<a href="https://doi.org/10.1007/978-3-030-24922-9\_26">10.1007/978-3-030-24922-9\_26</a>},
    booktitle={Proceedings of the 26th International Colloquium on Structural Information
    and Communication Complexity (SIROCCO)}, author={Castenow, Jannik and Kolb, Christina
    and Scheideler, Christian}, year={2019}, pages={345–348} }'
  chicago: Castenow, Jannik, Christina Kolb, and Christian Scheideler. “A Bounding
    Box Overlay for Competitive Routing in Hybrid Communication Networks.” In <i>Proceedings
    of the 26th International Colloquium on Structural Information and Communication
    Complexity (SIROCCO)</i>, 345–48, 2019. <a href="https://doi.org/10.1007/978-3-030-24922-9\_26">https://doi.org/10.1007/978-3-030-24922-9\_26</a>.
  ieee: J. Castenow, C. Kolb, and C. Scheideler, “A Bounding Box Overlay for Competitive
    Routing in Hybrid Communication Networks,” in <i>Proceedings of the 26th International
    Colloquium on Structural Information and Communication Complexity (SIROCCO)</i>,
    L’Aquila, Italy, 2019, pp. 345–348.
  mla: Castenow, Jannik, et al. “A Bounding Box Overlay for Competitive Routing in
    Hybrid Communication Networks.” <i>Proceedings of the 26th International Colloquium
    on Structural Information and Communication Complexity (SIROCCO)</i>, 2019, pp.
    345–48, doi:<a href="https://doi.org/10.1007/978-3-030-24922-9\_26">10.1007/978-3-030-24922-9\_26</a>.
  short: 'J. Castenow, C. Kolb, C. Scheideler, in: Proceedings of the 26th International
    Colloquium on Structural Information and Communication Complexity (SIROCCO), 2019,
    pp. 345–348.'
conference:
  end_date: 2019-07-04
  location: L'Aquila, Italy
  name: SIROCCO 2019
  start_date: 2019-07-01
date_created: 2019-11-04T10:09:35Z
date_updated: 2022-01-06T06:52:00Z
department:
- _id: '79'
- _id: '63'
doi: 10.1007/978-3-030-24922-9\_26
language:
- iso: eng
page: 345-348
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subproject A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 26th International Colloquium on Structural Information
  and Communication Complexity (SIROCCO)
status: public
title: A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks
type: conference
user_id: '477'
year: '2019'
...
---
_id: '13182'
abstract:
- lang: eng
  text: "We consider congestion control in peer-to-peer distributed systems. \r\nThe
    problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers
    (called \\emph{clients} in this paper) that want to send messages to a fixed common
    peer (called \\emph{server} in this paper).\r\nWe assume that each client $v \\in
    V$ sends a message with probability $p(v) \\in [0,1)$ and the server has a capacity
    of $\\sigma \\in \\mathbb{N}$, i.e., it can recieve at most $\\sigma$ messages
    per round and excess messages are dropped.\r\nThe server can modify these probabilities
    when clients send messages.\r\nIdeally, we wish to converge to a state with $\\sum
    p(v) = \\sigma$ and $p(v) = p(w)$ for all $v,w \\in V$.\t\r\n\r\nWe propose a
    \\emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state.
    \  \r\nOur protocol lets the system converge from \\emph{any} initial state to
    a state where $\\sum p(v) \\in \\left[\\sigma \\pm \\epsilon\\right]$ and $|p(v)-p(w)|
    \\in O(\\frac{1}{n})$. \r\nThis property is then maintained for $\\Omega(n^{\\mathfrak{c}})$
    rounds in expectation.\r\nIn particular, the initial client probabilities and
    server variables are not necessarily well-defined, i.e., they may have arbitrary
    values.\r\n\r\nOur protocol uses only $O(W + \\log n)$ bits of memory where $W$
    is length of node identifiers, making it very lightweight.\r\nFinally we state
    a lower bound on the convergence time an see that our protocol performs asymptotically
    optimal (up to some polylogarithmic factor).\r\n"
author:
- first_name: Michael
  full_name: Feldmann, Michael
  id: '23538'
  last_name: Feldmann
- first_name: Thorsten
  full_name: Götte, Thorsten
  id: '34727'
  last_name: Götte
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Feldmann M, Götte T, Scheideler C. A Loosely Self-stabilizing Protocol for
    Randomized Congestion Control with Logarithmic Memory. In: <i>Proceedings of the
    21st International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS)</i>. Lecture Notes in Computer Science. Springer, Cham; 2019:149-164.
    doi:<a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>'
  apa: Feldmann, M., Götte, T., &#38; Scheideler, C. (2019). A Loosely Self-stabilizing
    Protocol for Randomized Congestion Control with Logarithmic Memory. In <i>Proceedings
    of the 21st International Symposium on Stabilization, Safety, and Security of
    Distributed Systems (SSS)</i> (pp. 149–164). Springer, Cham. <a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>
  bibtex: '@inproceedings{Feldmann_Götte_Scheideler_2019, series={Lecture Notes in
    Computer Science}, title={A Loosely Self-stabilizing Protocol for Randomized Congestion
    Control with Logarithmic Memory}, DOI={<a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>},
    booktitle={Proceedings of the 21st International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann,
    Michael and Götte, Thorsten and Scheideler, Christian}, year={2019}, pages={149–164},
    collection={Lecture Notes in Computer Science} }'
  chicago: Feldmann, Michael, Thorsten Götte, and Christian Scheideler. “A Loosely
    Self-Stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory.”
    In <i>Proceedings of the 21st International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, 149–64. Lecture Notes in Computer
    Science. Springer, Cham, 2019. <a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>.
  ieee: M. Feldmann, T. Götte, and C. Scheideler, “A Loosely Self-stabilizing Protocol
    for Randomized Congestion Control with Logarithmic Memory,” in <i>Proceedings
    of the 21st International Symposium on Stabilization, Safety, and Security of
    Distributed Systems (SSS)</i>, 2019, pp. 149–164.
  mla: Feldmann, Michael, et al. “A Loosely Self-Stabilizing Protocol for Randomized
    Congestion Control with Logarithmic Memory.” <i>Proceedings of the 21st International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>,
    Springer, Cham, 2019, pp. 149–64, doi:<a href="https://doi.org/10.1007/978-3-030-34992-9_13">https://doi.org/10.1007/978-3-030-34992-9_13</a>.
  short: 'M. Feldmann, T. Götte, C. Scheideler, in: Proceedings of the 21st International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
    Springer, Cham, 2019, pp. 149–164.'
date_created: 2019-09-10T12:48:33Z
date_updated: 2022-01-06T06:51:30Z
ddc:
- '000'
department:
- _id: '79'
doi: https://doi.org/10.1007/978-3-030-34992-9_13
external_id:
  arxiv:
  - '1909.04544'
file:
- access_level: closed
  content_type: application/pdf
  creator: mfeldma2
  date_created: 2019-09-11T11:20:16Z
  date_updated: 2019-09-11T11:20:16Z
  file_id: '13188'
  file_name: main.pdf
  file_size: 428908
  relation: main_file
  success: 1
file_date_updated: 2019-09-11T11:20:16Z
has_accepted_license: '1'
language:
- iso: eng
page: 149-164
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 21st International Symposium on Stabilization, Safety,
  and Security of Distributed Systems (SSS)
publisher: Springer, Cham
series_title: Lecture Notes in Computer Science
status: public
title: A Loosely Self-stabilizing Protocol for Randomized Congestion Control with
  Logarithmic Memory
type: conference
user_id: '23538'
year: '2019'
...