---
_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: '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: '3422'
abstract:
- lang: eng
  text: "We study the consensus problem in a synchronous distributed system of n nodes
    under an adaptive adversary that has a slightly outdated view of the system and
    can block all incoming and outgoing communication of a constant fraction of the
    nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing
    that any consensus algorithm that is resilient against a linear number of crash
    faults requires $\\tilde \\Omega(\\sqrt n)$ rounds in an n-node network against
    an adaptive adversary, we consider a late adaptive adversary, who has full knowledge
    of the network state at the beginning of the previous round and unlimited computational
    power, but is oblivious to the current state of the nodes. \r\n\r\nOur main contributions
    are randomized distributed algorithms that achieve consensus with high probability
    among all except a small constant fraction of the nodes (i.e., \"almost-everywhere'')
    against a late adaptive adversary who can block up to ε n$ nodes in each round,
    for a small constant ε >0$. Our first protocol achieves binary almost-everywhere
    consensus and also guarantees a decision on the majority input value, thus ensuring
    plurality consensus. We also present an algorithm that achieves the same time
    complexity for multi-value consensus. Both of our algorithms succeed in $O(log
    n)$ rounds with high probability, thus showing an exponential gap to the $\\tilde\\Omega(\\sqrt
    n)$ lower bound of Ben-Or and Bar-Joseph for strongly adaptive crash-failure adversaries,
    which can be strengthened to $\\Omega(n)$ when allowing the adversary to block
    nodes instead of permanently crashing them. Our algorithms are scalable to large
    systems as each node contacts only an (amortized) constant number of peers in
    each communication round. We show that our algorithms are optimal up to constant
    (resp.\\ sub-logarithmic) factors by proving that every almost-everywhere consensus
    protocol takes $\\Omega(log_d n)$ rounds in the worst case, where d is an upper
    bound on the number of communication requests initiated per node in each round.
    We complement our theoretical results with an experimental evaluation of the binary
    almost-everywhere consensus protocol revealing a short convergence time even against
    an adversary blocking a large fraction of nodes."
author:
- first_name: Peter
  full_name: Robinson, Peter
  last_name: Robinson
- 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: 'Robinson P, Scheideler C, Setzer A. Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary. In: <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. doi:<a
    href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>'
  apa: 'Robinson, P., Scheideler, C., &#38; Setzer, A. (n.d.). Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary. In <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. Wien.
    <a href="https://doi.org/10.1145/3210377.3210399">https://doi.org/10.1145/3210377.3210399</a>'
  bibtex: '@inproceedings{Robinson_Scheideler_Setzer, title={Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary}, DOI={<a href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>},
    booktitle={Proceedings of the 30th ACM Symposium on Parallelism in Algorithms
    and Architectures (SPAA)}, author={Robinson, Peter and Scheideler, Christian and
    Setzer, Alexander} }'
  chicago: 'Robinson, Peter, Christian Scheideler, and Alexander Setzer. “Breaking
    the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary.”
    In <i>Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures
    (SPAA)</i>, n.d. <a href="https://doi.org/10.1145/3210377.3210399">https://doi.org/10.1145/3210377.3210399</a>.'
  ieee: 'P. Robinson, C. Scheideler, and A. Setzer, “Breaking the $\tilde\Omega(\sqrt{n})$
    Barrier: Fast Consensus under a Late Adversary,” in <i>Proceedings of the 30th
    ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>, Wien.'
  mla: 'Robinson, Peter, et al. “Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast
    Consensus under a Late Adversary.” <i>Proceedings of the 30th ACM Symposium on
    Parallelism in Algorithms and Architectures (SPAA)</i>, doi:<a href="https://doi.org/10.1145/3210377.3210399">10.1145/3210377.3210399</a>.'
  short: 'P. Robinson, C. Scheideler, A. Setzer, in: Proceedings of the 30th ACM Symposium
    on Parallelism in Algorithms and Architectures (SPAA), n.d.'
conference:
  end_date: 2018-07-18
  location: Wien
  name: 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
  start_date: 2018-07-16
date_created: 2018-07-04T08:55:45Z
date_updated: 2022-01-06T06:59:16Z
ddc:
- '040'
department:
- _id: '79'
- _id: '34'
- _id: '7'
doi: 10.1145/3210377.3210399
file:
- access_level: closed
  content_type: application/pdf
  creator: asetzer
  date_created: 2018-10-31T13:30:40Z
  date_updated: 2018-10-31T13:30:40Z
  file_id: '5215'
  file_name: p173-robinson.pdf
  file_size: 1675407
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T13:30:40Z
has_accepted_license: '1'
keyword:
- distributed consensus
- randomized algorithm
- adaptive adversary
- complexity lower bound
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 30th ACM Symposium on Parallelism in Algorithms and
  Architectures (SPAA)
publication_identifier:
  isbn:
  - 978-1-4503-5799-9/18/07
publication_status: accepted
status: public
title: 'Breaking the $\tilde\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late
  Adversary'
type: conference
user_id: '11108'
year: '2018'
...
---
_id: '1164'
abstract:
- lang: eng
  text: "We propose a distributed protocol for a queue, called Skueue, which spreads
    its data fairly onto multiple processes, avoiding bottlenecks in high throughput
    scenarios.\r\nSkueuecan be used in highly dynamic environments, through the addition
    of join and leave requests to the standard queue operations enqueue and dequeue.\r\nFurthermore
    Skueue satisfies sequential consistency in the asynchronous message passing model.\r\nScalability
    is achieved by aggregating multiple requests to a batch, which can then be processed
    in a distributed fashion without hurting the queue semantics.\r\nOperations in
    Skueue need a logarithmic number of rounds w.h.p. until they are processed, even
    under a high rate of incoming requests."
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: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Feldmann M, Scheideler C, Setzer A. Skueue: A Scalable and Sequentially Consistent
    Distributed Queue. In: <i>Proceedings of the 32nd IEEE International Parallel
    &#38; Distributed Processing Symposium (IPDPS)</i>. IEEE; 2018. doi:<a href="https://doi.org/10.1109/IPDPS.2018.00113">10.1109/IPDPS.2018.00113</a>'
  apa: 'Feldmann, M., Scheideler, C., &#38; Setzer, A. (2018). Skueue: A Scalable
    and Sequentially Consistent Distributed Queue. In <i>Proceedings of the 32nd IEEE
    International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>. Vancouver:
    IEEE. <a href="https://doi.org/10.1109/IPDPS.2018.00113">https://doi.org/10.1109/IPDPS.2018.00113</a>'
  bibtex: '@inproceedings{Feldmann_Scheideler_Setzer_2018, title={Skueue: A Scalable
    and Sequentially Consistent Distributed Queue}, DOI={<a href="https://doi.org/10.1109/IPDPS.2018.00113">10.1109/IPDPS.2018.00113</a>},
    booktitle={Proceedings of the 32nd IEEE International Parallel &#38; Distributed
    Processing Symposium (IPDPS)}, publisher={IEEE}, author={Feldmann, Michael and
    Scheideler, Christian and Setzer, Alexander}, year={2018} }'
  chicago: 'Feldmann, Michael, Christian Scheideler, and Alexander Setzer. “Skueue:
    A Scalable and Sequentially Consistent Distributed Queue.” In <i>Proceedings of
    the 32nd IEEE International Parallel &#38; Distributed Processing Symposium (IPDPS)</i>.
    IEEE, 2018. <a href="https://doi.org/10.1109/IPDPS.2018.00113">https://doi.org/10.1109/IPDPS.2018.00113</a>.'
  ieee: 'M. Feldmann, C. Scheideler, and A. Setzer, “Skueue: A Scalable and Sequentially
    Consistent Distributed Queue,” in <i>Proceedings of the 32nd IEEE International
    Parallel &#38; Distributed Processing Symposium (IPDPS)</i>, Vancouver, 2018.'
  mla: 'Feldmann, Michael, et al. “Skueue: A Scalable and Sequentially Consistent
    Distributed Queue.” <i>Proceedings of the 32nd IEEE International Parallel &#38;
    Distributed Processing Symposium (IPDPS)</i>, IEEE, 2018, doi:<a href="https://doi.org/10.1109/IPDPS.2018.00113">10.1109/IPDPS.2018.00113</a>.'
  short: 'M. Feldmann, C. Scheideler, A. Setzer, in: Proceedings of the 32nd IEEE
    International Parallel &#38; Distributed Processing Symposium (IPDPS), IEEE, 2018.'
conference:
  end_date: 2018-5-24
  location: Vancouver
  name: 32nd IEEE International Parallel & Distributed Processing Symposium (IPDPS)
  start_date: 2018-5-22
date_created: 2018-02-01T14:00:36Z
date_updated: 2022-01-06T06:51:05Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/IPDPS.2018.00113
external_id:
  arxiv:
  - '1802.07504'
file:
- access_level: closed
  content_type: application/pdf
  creator: mfeldma2
  date_created: 2018-10-31T13:29:26Z
  date_updated: 2018-10-31T13:29:26Z
  file_id: '5212'
  file_name: 08425257.pdf
  file_size: 218420
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T13:29:26Z
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
publication: Proceedings of the 32nd IEEE International Parallel & Distributed Processing
  Symposium (IPDPS)
publisher: IEEE
status: public
title: 'Skueue: A Scalable and Sequentially Consistent Distributed Queue'
type: conference
user_id: '23538'
year: '2018'
...
---
_id: '5820'
abstract:
- lang: eng
  text: "In this paper, we investigate the use of trusted execution environments (TEEs,
    such as Intel's SGX) for an anonymous communication infrastructure over untrusted
    networks.\r\nFor this, we present the general idea of exploiting trusted execution
    environments for the purpose of anonymous communication, including a continuous-time
    security framework that models strong anonymity guarantees in the presence of
    an adversary that observes all network traffic and can adaptively corrupt a constant
    fraction of participating nodes.\r\nIn our framework, a participating node can
    generate a number of unlinkable pseudonyms. Messages are sent from and to pseudonyms,
    allowing both senders and receivers of messages to remain anonymous. We introduce
    a concrete construction, which shows viability of our TEE-based approach to anonymous
    communication. The construction draws from techniques from cryptography and overlay
    networks. \r\nOur techniques are very general and can be used as a basis for future
    constructions with similar goals."
author:
- first_name: Johannes
  full_name: Blömer, Johannes
  id: '23'
  last_name: Blömer
- first_name: Jan
  full_name: Bobolz, Jan
  id: '27207'
  last_name: Bobolz
- 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: Blömer J, Bobolz J, Scheideler C, Setzer A. <i>Provably Anonymous Communication
    Based on Trusted Execution Environments</i>.
  apa: Blömer, J., Bobolz, J., Scheideler, C., &#38; Setzer, A. (n.d.). <i>Provably
    Anonymous Communication Based on Trusted Execution Environments</i>.
  bibtex: '@book{Blömer_Bobolz_Scheideler_Setzer, title={Provably Anonymous Communication
    Based on Trusted Execution Environments}, author={Blömer, Johannes and Bobolz,
    Jan and Scheideler, Christian and Setzer, Alexander} }'
  chicago: Blömer, Johannes, Jan Bobolz, Christian Scheideler, and Alexander Setzer.
    <i>Provably Anonymous Communication Based on Trusted Execution Environments</i>,
    n.d.
  ieee: J. Blömer, J. Bobolz, C. Scheideler, and A. Setzer, <i>Provably Anonymous
    Communication Based on Trusted Execution Environments</i>. .
  mla: Blömer, Johannes, et al. <i>Provably Anonymous Communication Based on Trusted
    Execution Environments</i>.
  short: J. Blömer, J. Bobolz, C. Scheideler, A. Setzer, Provably Anonymous Communication
    Based on Trusted Execution Environments, n.d.
date_created: 2018-11-25T08:08:40Z
date_updated: 2022-01-06T07:02:43Z
ddc:
- '000'
department:
- _id: '7'
- _id: '64'
- _id: '79'
file:
- access_level: closed
  content_type: application/pdf
  creator: jbobolz
  date_created: 2018-12-31T09:55:30Z
  date_updated: 2018-12-31T09:55:30Z
  file_id: '6435'
  file_name: draft-2018.pdf
  file_size: 470968
  relation: main_file
  success: 1
file_date_updated: 2018-12-31T09:55:30Z
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_status: draft
status: public
title: Provably Anonymous Communication Based on Trusted Execution Environments
type: working_paper
user_id: '27207'
year: '2018'
...
---
_id: '4375'
abstract:
- lang: eng
  text: "We present a peer-to-peer network that supports the efficient processing
    of orthogonal range queries $R=\\bigtimes_{i=1}^{d}[a_i,\\,b_i]$ in a $d$-dimensional
    point space.\\\\\r\nThe  network is the same for each dimension, namely a distance
    halving network like the one introduced by Naor and Wieder (ACM TALG'07).\r\nWe
    show how to execute such range queries using $\\mathcal{O}\\left(2^{d'}d\\,\\log
    m + d\\,|R|\\right)$ hops (and the same number of messages) in total. Here $[m]^d$
    is the ground set, $|R|$ is the size and $d'$ the dimension of the queried range.\r\nFurthermore,
    if the peers form a distributed network, the query can be answered in $\\mathcal{O}\\left(d\\,\\log
    m + d\\,\\sum_{i=1}^{d}(b_i-a_i+1)\\right)$ communication rounds.\r\nOur algorithms
    are based on a mapping of the Hilbert Curve through $[m]^d$ to the peers."
author:
- first_name: Markus
  full_name: Benter, Markus
  last_name: Benter
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
- first_name: Jannik
  full_name: Sundermeier, Jannik
  id: '38705'
  last_name: Sundermeier
citation:
  ama: 'Benter M, Knollmann T, Meyer auf der Heide F, Setzer A, Sundermeier J. A Peer-to-Peer
    based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension.
    In: <i>Proceedings of the 4th International Symposium on Algorithmic Aspects of
    Cloud Computing (ALGOCLOUD)</i>. ; 2018. doi:<a href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a>'
  apa: Benter, M., Knollmann, T., Meyer auf der Heide, F., Setzer, A., &#38; Sundermeier,
    J. (2018). A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
    of arbitrary Dimension. In <i>Proceedings of the 4th International Symposium on
    Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>. Helsinki. <a href="https://doi.org/10.1007/978-3-030-19759-9_4">https://doi.org/10.1007/978-3-030-19759-9_4</a>
  bibtex: '@inproceedings{Benter_Knollmann_Meyer auf der Heide_Setzer_Sundermeier_2018,
    title={A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
    of arbitrary Dimension}, DOI={<a href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a>},
    booktitle={Proceedings of the 4th International Symposium on Algorithmic Aspects
    of Cloud Computing (ALGOCLOUD)}, author={Benter, Markus and Knollmann, Till and
    Meyer auf der Heide, Friedhelm and Setzer, Alexander and Sundermeier, Jannik},
    year={2018} }'
  chicago: Benter, Markus, Till Knollmann, Friedhelm Meyer auf der Heide, Alexander
    Setzer, and Jannik Sundermeier. “A Peer-to-Peer Based Cloud Storage Supporting
    Orthogonal Range Queries of Arbitrary Dimension.” In <i>Proceedings of the 4th
    International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>,
    2018. <a href="https://doi.org/10.1007/978-3-030-19759-9_4">https://doi.org/10.1007/978-3-030-19759-9_4</a>.
  ieee: M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, and J. Sundermeier,
    “A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
    Dimension,” in <i>Proceedings of the 4th International Symposium on Algorithmic
    Aspects of Cloud Computing (ALGOCLOUD)</i>, Helsinki, 2018.
  mla: Benter, Markus, et al. “A Peer-to-Peer Based Cloud Storage Supporting Orthogonal
    Range Queries of Arbitrary Dimension.” <i>Proceedings of the 4th International
    Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)</i>, 2018, doi:<a
    href="https://doi.org/10.1007/978-3-030-19759-9_4">10.1007/978-3-030-19759-9_4</a>.
  short: 'M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier,
    in: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud
    Computing (ALGOCLOUD), 2018.'
conference:
  end_date: 2018-08-21
  location: Helsinki
  name: 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD)
  start_date: 2018-08-20
date_created: 2018-09-11T05:26:59Z
date_updated: 2022-01-06T07:01:00Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-19759-9_4
file:
- access_level: closed
  content_type: application/pdf
  creator: tillk
  date_created: 2018-11-27T10:03:33Z
  date_updated: 2018-11-27T10:03:33Z
  file_id: '5863'
  file_name: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries
    of arbitrary Dimension.pdf
  file_size: 1122875
  relation: main_file
  success: 1
file_date_updated: 2018-11-27T10:03:33Z
has_accepted_license: '1'
keyword:
- Distributed Storage
- Multi-Dimensional Range Queries
- Peer-to-Peer
- Hilbert Curve
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 4th International Symposium on Algorithmic Aspects
  of Cloud Computing (ALGOCLOUD)
status: public
title: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary
  Dimension
type: conference
user_id: '14955'
year: '2018'
...
---
_id: '5216'
abstract:
- lang: eng
  text: A fundamental problem for overlay networks is to safely exclude leaving nodes,
    i.e., the nodes requesting to leave the overlay network are excluded from it without
    affecting its connectivity. To rigorously study self-stabilizing solutions to
    this problem, the Finite Departure Problem (FDP) has been proposed [9]. In the
    FDP we are given a network of processes in an arbitrary state, and the goal is
    to eventually arrive at (and stay in) a state in which all leaving processes irrevocably
    decided to leave the system while for all weakly-connected components in the initial
    overlay network, all staying processes in that component will still form a weakly
    connected component. In the standard interconnection model, the FDP is known to
    be unsolvable by local control protocols, so oracles have been investigated that
    allow the problem to be solved [9]. To avoid the use of oracles, we introduce
    a new interconnection model based on relays. Despite the relay model appearing
    to be rather restrictive, we show that it is universal, i.e., it is possible to
    transform any weakly-connected topology into any other weakly-connected topology,
    which is important for being a useful interconnection model for overlay networks.
    Apart from this, our model allows processes to grant and revoke access rights,
    which is why we believe it to be of interest beyond the scope of this paper. We
    show how to implement the relay layer in a self-stabilizing way and identify properties
    protocols need to satisfy so that the relay layer can recover while serving protocol
    requests.
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. Relays: A New Approach for the Finite Departure Problem
    in Overlay Networks. In: <i>Proceedings of the 20th International Symposium on
    Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>. ; 2018.
    doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_16">10.1007/978-3-030-03232-6_16</a>'
  apa: 'Scheideler, C., &#38; Setzer, A. (2018). Relays: A New Approach for the Finite
    Departure Problem in Overlay Networks. In <i>Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>.
    Tokyo, Japan. <a href="https://doi.org/10.1007/978-3-030-03232-6_16">https://doi.org/10.1007/978-3-030-03232-6_16</a>'
  bibtex: '@inproceedings{Scheideler_Setzer_2018, title={Relays: A New Approach for
    the Finite Departure Problem in Overlay Networks}, DOI={<a href="https://doi.org/10.1007/978-3-030-03232-6_16">10.1007/978-3-030-03232-6_16</a>},
    booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS 2018)}, author={Scheideler, Christian
    and Setzer, Alexander}, year={2018} }'
  chicago: 'Scheideler, Christian, and Alexander Setzer. “Relays: A New Approach for
    the Finite Departure Problem in Overlay Networks.” In <i>Proceedings of the 20th
    International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS 2018)</i>, 2018. <a href="https://doi.org/10.1007/978-3-030-03232-6_16">https://doi.org/10.1007/978-3-030-03232-6_16</a>.'
  ieee: 'C. Scheideler and A. Setzer, “Relays: A New Approach for the Finite Departure
    Problem in Overlay Networks,” in <i>Proceedings of the 20th International Symposium
    on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>,
    Tokyo, Japan, 2018.'
  mla: 'Scheideler, Christian, and Alexander Setzer. “Relays: A New Approach for the
    Finite Departure Problem in Overlay Networks.” <i>Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>,
    2018, doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_16">10.1007/978-3-030-03232-6_16</a>.'
  short: 'C. Scheideler, A. Setzer, in: Proceedings of the 20th International Symposium
    on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), 2018.'
conference:
  location: Tokyo, Japan
  name: 20th International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS 2018)
date_created: 2018-10-31T13:33:05Z
date_updated: 2022-01-06T07:01:47Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-030-03232-6_16
file:
- access_level: closed
  content_type: application/pdf
  creator: asetzer
  date_created: 2018-10-31T15:51:45Z
  date_updated: 2018-10-31T16:09:48Z
  file_id: '5223'
  file_name: Scheideler-Setzer2018_Chapter_RelaysANewApproachForTheFinite.pdf
  file_size: 369818
  relation: main_file
file_date_updated: 2018-10-31T16:09:48Z
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 20th International Symposium on Stabilization, Safety,
  and Security of Distributed Systems (SSS 2018)
publication_status: published
status: public
title: 'Relays: A New Approach for the Finite Departure Problem in Overlay Networks'
type: conference
user_id: '11108'
year: '2018'
...
---
_id: '5222'
abstract:
- lang: eng
  text: 'We present a self-stabilizing protocol for an overlay network that constructs
    the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted
    tree. The weight of an overlay edge between two nodes is the weighted length of
    their shortest path in the tree. We rigorously prove that our protocol works correctly
    under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes
    after O(N^2) asynchronous rounds where N is the number of nodes in the overlay. '
author:
- 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
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Götte T, Scheideler C, Setzer A. On Underlay-Aware Self-Stabilizing Overlay
    Networks. In: <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS 2018)</i>. Vol 11201. Lecture
    Notes in Computer Science. Springer; 2018:50-64.'
  apa: 'Götte, T., Scheideler, C., &#38; Setzer, A. (2018). On Underlay-Aware Self-Stabilizing
    Overlay Networks. In <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS 2018)</i> (Vol. 11201, pp. 50–64).
    Tokyo, Japan: Springer.'
  bibtex: '@inproceedings{Götte_Scheideler_Setzer_2018, series={Lecture Notes in Computer
    Science}, title={On Underlay-Aware Self-Stabilizing Overlay Networks}, volume={11201},
    booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS 2018)}, publisher={Springer}, author={Götte,
    Thorsten and Scheideler, Christian and Setzer, Alexander}, year={2018}, pages={50–64},
    collection={Lecture Notes in Computer Science} }'
  chicago: Götte, Thorsten, Christian Scheideler, and Alexander Setzer. “On Underlay-Aware
    Self-Stabilizing Overlay Networks.” In <i>Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>,
    11201:50–64. Lecture Notes in Computer Science. Springer, 2018.
  ieee: T. Götte, C. Scheideler, and A. Setzer, “On Underlay-Aware Self-Stabilizing
    Overlay Networks,” in <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS 2018)</i>, Tokyo, Japan, 2018,
    vol. 11201, pp. 50–64.
  mla: Götte, Thorsten, et al. “On Underlay-Aware Self-Stabilizing Overlay Networks.”
    <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and
    Security of Distributed Systems (SSS 2018)</i>, vol. 11201, Springer, 2018, pp.
    50–64.
  short: 'T. Götte, C. Scheideler, A. Setzer, in: Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018),
    Springer, 2018, pp. 50–64.'
conference:
  location: Tokyo, Japan
  name: ' 20th International Symposium on Stabilization, Safety, and Security of Distributed
    Systems (SSS 2018)'
date_created: 2018-10-31T15:44:30Z
date_updated: 2022-01-06T07:01:47Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: closed
  content_type: application/pdf
  creator: thgoette
  date_created: 2018-10-31T15:59:26Z
  date_updated: 2018-10-31T15:59:26Z
  file_id: '5224'
  file_name: sss18_camera.pdf
  file_size: 367812
  relation: main_file
  success: 1
file_date_updated: 2018-10-31T15:59:26Z
has_accepted_license: '1'
intvolume: '     11201'
language:
- iso: eng
page: 50-64
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 20th International Symposium on Stabilization, Safety,
  and Security of Distributed Systems (SSS 2018)
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: On Underlay-Aware Self-Stabilizing Overlay Networks
type: conference
user_id: '477'
volume: 11201
year: '2018'
...
---
_id: '142'
abstract:
- lang: eng
  text: For overlay networks, the ability to recover from a variety of problems like
    membership changes or faults is a key element to preserve their functionality.
    In recent years, various self-stabilizing overlay networks have been proposed
    that have the advantage of being able to recover from any illegal state. However,
    the vast majority of these networks cannot give any guarantees on its functionality
    while the recovery process is going on. We are especially interested in searchability,
    i.e., the functionality that search messages for a specific identifier are answered
    successfully if a node with that identifier exists in the network. We investigate
    overlay networks that are not only self-stabilizing but that also ensure that
    monotonic searchability is maintained while the recovery process is going on,
    as long as there are no corrupted messages in the system. More precisely, once
    a search message from node u to another node v is successfully delivered, all
    future search messages from u to v succeed as well. Monotonic searchability was
    recently introduced in OPODIS 2015, in which the authors provide a solution for
    a simple line topology.We present the first universal approach to maintain monotonic
    searchability that is applicable to a wide range of topologies. As the base for
    our approach, we introduce a set of primitives for manipulating overlay networks
    that allows us to maintain searchability and show how existing protocols can be
    transformed to use theses primitives.We complement this result with a generic
    search protocol that together with the use of our primitives guarantees monotonic
    searchability.As an additional feature, searching existing nodes with the generic
    search protocol is as fast as searching a node with any other fixed routing protocol
    once the topology has stabilized.
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
- first_name: Thim Frederik
  full_name: Strothmann, Thim Frederik
  id: '11319'
  last_name: Strothmann
citation:
  ama: 'Scheideler C, Setzer A, Strothmann TF. Towards a Universal Approach for Monotonic
    Searchability in Self-stabilizing Overlay Networks. In: <i>Proceedings of the
    30th International Symposium on Distributed Computing (DISC)</i>. LNCS. ; 2016:71--84.
    doi:<a href="https://doi.org/10.1007/978-3-662-53426-7_6">10.1007/978-3-662-53426-7_6</a>'
  apa: Scheideler, C., Setzer, A., &#38; Strothmann, T. F. (2016). Towards a Universal
    Approach for Monotonic Searchability in Self-stabilizing Overlay Networks. In
    <i>Proceedings of the 30th International Symposium on Distributed Computing (DISC)</i>
    (pp. 71--84). <a href="https://doi.org/10.1007/978-3-662-53426-7_6">https://doi.org/10.1007/978-3-662-53426-7_6</a>
  bibtex: '@inproceedings{Scheideler_Setzer_Strothmann_2016, series={LNCS}, title={Towards
    a Universal Approach for Monotonic Searchability in Self-stabilizing Overlay Networks},
    DOI={<a href="https://doi.org/10.1007/978-3-662-53426-7_6">10.1007/978-3-662-53426-7_6</a>},
    booktitle={Proceedings of the 30th International Symposium on Distributed Computing
    (DISC)}, author={Scheideler, Christian and Setzer, Alexander and Strothmann, Thim
    Frederik}, year={2016}, pages={71--84}, collection={LNCS} }'
  chicago: Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann.
    “Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing
    Overlay Networks.” In <i>Proceedings of the 30th International Symposium on Distributed
    Computing (DISC)</i>, 71--84. LNCS, 2016. <a href="https://doi.org/10.1007/978-3-662-53426-7_6">https://doi.org/10.1007/978-3-662-53426-7_6</a>.
  ieee: C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards a Universal Approach
    for Monotonic Searchability in Self-stabilizing Overlay Networks,” in <i>Proceedings
    of the 30th International Symposium on Distributed Computing (DISC)</i>, 2016,
    pp. 71--84.
  mla: Scheideler, Christian, et al. “Towards a Universal Approach for Monotonic Searchability
    in Self-Stabilizing Overlay Networks.” <i>Proceedings of the 30th International
    Symposium on Distributed Computing (DISC)</i>, 2016, pp. 71--84, doi:<a href="https://doi.org/10.1007/978-3-662-53426-7_6">10.1007/978-3-662-53426-7_6</a>.
  short: 'C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 30th International
    Symposium on Distributed Computing (DISC), 2016, pp. 71--84.'
date_created: 2017-10-17T12:41:19Z
date_updated: 2022-01-06T06:51:56Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-662-53426-7_6
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-21T12:59:29Z
  date_updated: 2018-03-21T12:59:29Z
  file_id: '1558'
  file_name: 142-SchSetStrDISC16.pdf
  file_size: 209638
  relation: main_file
  success: 1
file_date_updated: 2018-03-21T12:59:29Z
has_accepted_license: '1'
language:
- iso: eng
page: 71--84
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 30th International Symposium on Distributed Computing
  (DISC)
series_title: LNCS
status: public
title: Towards a Universal Approach for Monotonic Searchability in Self-stabilizing
  Overlay Networks
type: conference
user_id: '477'
year: '2016'
...
---
_id: '241'
abstract:
- lang: eng
  text: Distributed applications are commonly based on overlay networks interconnecting
    their sites so that they can exchange information. For these overlay networks
    to preserve their functionality, they should be able to recover from various problems
    like membership changes or faults. Various self-stabilizing overlay networks have
    already been proposed in recent years, which have the advantage of being able
    to recover from any illegal state, but none of these networks can give any guarantees
    on its functionality while the recovery process is going on. We initiate research
    on overlay networks that are not only self-stabilizing but that also ensure that
    searchability is maintained while the recovery process is going on, as long as
    there are no corrupted messages in the system. More precisely, once a search message
    from node u to another node v is successfully delivered, all future search messages
    from u to v succeed as well. We call this property monotonic searchability. We
    show that in general it is impossible to provide monotonic searchability if corrupted
    messages are present in the system, which justifies the restriction to system
    states without corrupted messages. Furthermore, we provide a self-stabilizing
    protocol for the line for which we can also show monotonic searchability. It turns
    out that even for the line it is non-trivial to achieve this property. Additionally,
    we extend our protocol to deal with node departures in terms of the Finite Departure
    Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of
    handling node dynamics.
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
- first_name: Thim Frederik
  full_name: Strothmann, Thim Frederik
  id: '11319'
  last_name: Strothmann
citation:
  ama: 'Scheideler C, Setzer A, Strothmann TF. Towards Establishing Monotonic Searchability
    in Self-Stabilizing Data Structures. In: <i>Proceedings of the 19th International
    Conference on Principles of Distributed Systems (OPODIS)</i>. Leibniz International
    Proceedings in Informatics (LIPIcs). ; 2015. doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2015.24">10.4230/LIPIcs.OPODIS.2015.24</a>'
  apa: Scheideler, C., Setzer, A., &#38; Strothmann, T. F. (2015). Towards Establishing
    Monotonic Searchability in Self-Stabilizing Data Structures. In <i>Proceedings
    of the 19th International Conference on Principles of Distributed Systems (OPODIS)</i>.
    <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2015.24">https://doi.org/10.4230/LIPIcs.OPODIS.2015.24</a>
  bibtex: '@inproceedings{Scheideler_Setzer_Strothmann_2015, series={Leibniz International
    Proceedings in Informatics (LIPIcs)}, title={Towards Establishing Monotonic Searchability
    in Self-Stabilizing Data Structures}, DOI={<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2015.24">10.4230/LIPIcs.OPODIS.2015.24</a>},
    booktitle={Proceedings of the 19th International Conference on Principles of Distributed
    Systems (OPODIS)}, author={Scheideler, Christian and Setzer, Alexander and Strothmann,
    Thim Frederik}, year={2015}, collection={Leibniz International Proceedings in
    Informatics (LIPIcs)} }'
  chicago: Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann.
    “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.”
    In <i>Proceedings of the 19th International Conference on Principles of Distributed
    Systems (OPODIS)</i>. Leibniz International Proceedings in Informatics (LIPIcs),
    2015. <a href="https://doi.org/10.4230/LIPIcs.OPODIS.2015.24">https://doi.org/10.4230/LIPIcs.OPODIS.2015.24</a>.
  ieee: C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards Establishing Monotonic
    Searchability in Self-Stabilizing Data Structures,” in <i>Proceedings of the 19th
    International Conference on Principles of Distributed Systems (OPODIS)</i>, 2015.
  mla: Scheideler, Christian, et al. “Towards Establishing Monotonic Searchability
    in Self-Stabilizing Data Structures.” <i>Proceedings of the 19th International
    Conference on Principles of Distributed Systems (OPODIS)</i>, 2015, doi:<a href="https://doi.org/10.4230/LIPIcs.OPODIS.2015.24">10.4230/LIPIcs.OPODIS.2015.24</a>.
  short: 'C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 19th International
    Conference on Principles of Distributed Systems (OPODIS), 2015.'
date_created: 2017-10-17T12:41:39Z
date_updated: 2022-01-06T06:56:07Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.4230/LIPIcs.OPODIS.2015.24
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-21T10:28:21Z
  date_updated: 2018-03-21T10:28:21Z
  file_id: '1497'
  file_name: 241-ScheidelerSetzerStrothmann2015.pdf
  file_size: 692363
  relation: main_file
  success: 1
file_date_updated: 2018-03-21T10:28:21Z
has_accepted_license: '1'
language:
- iso: eng
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 19th International Conference on Principles of Distributed
  Systems (OPODIS)
series_title: Leibniz International Proceedings in Informatics (LIPIcs)
status: public
title: Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures
type: conference
user_id: '477'
year: '2015'
...
---
_id: '371'
abstract:
- lang: eng
  text: In this work we present the first distributed storage system that is provably
    robust against crash failures issued by an adaptive adversary, i.e., for each
    batch of requests the adversary can decide based on the entire system state which
    servers will be unavailable for that batch of requests. Despite up to \gamma n^{1/\log\log
    n} crashed servers, with \gamma>0 constant and n denoting the number of servers,
    our system can correctly process any batch of lookup and write requests (with
    at most a polylogarithmic number of requests issued at each non-crashed server)
    in at most a polylogarithmic number of communication rounds, with at most polylogarithmic
    time and work at each server and only a logarithmic storage overhead. Our system
    is based on previous work by Eikel and Scheideler (SPAA 2013), who presented IRIS,
    a distributed information system that is provably robust against the same kind
    of crash failures. However, IRIS is only able to serve lookup requests. Handling
    both lookup and write requests has turned out to require major changes in the
    design of IRIS.
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
- first_name: Martina
  full_name: Eikel, Martina
  last_name: Eikel
citation:
  ama: 'Scheideler C, Setzer A, Eikel M. RoBuSt: A Crash-Failure-Resistant Distributed
    Storage System. In: <i>Proceedings of the 18th International Conference on Principles
    of Distributed Systems (OPODIS)</i>. LNCS. ; 2014:107--122. doi:<a href="https://doi.org/10.1007/978-3-319-14472-6_8">10.1007/978-3-319-14472-6_8</a>'
  apa: 'Scheideler, C., Setzer, A., &#38; Eikel, M. (2014). RoBuSt: A Crash-Failure-Resistant
    Distributed Storage System. In <i>Proceedings of the 18th International Conference
    on Principles of Distributed Systems (OPODIS)</i> (pp. 107--122). <a href="https://doi.org/10.1007/978-3-319-14472-6_8">https://doi.org/10.1007/978-3-319-14472-6_8</a>'
  bibtex: '@inproceedings{Scheideler_Setzer_Eikel_2014, series={LNCS}, title={RoBuSt:
    A Crash-Failure-Resistant Distributed Storage System}, DOI={<a href="https://doi.org/10.1007/978-3-319-14472-6_8">10.1007/978-3-319-14472-6_8</a>},
    booktitle={Proceedings of the 18th International Conference on Principles of Distributed
    Systems (OPODIS)}, author={Scheideler, Christian and Setzer, Alexander and Eikel,
    Martina}, year={2014}, pages={107--122}, collection={LNCS} }'
  chicago: 'Scheideler, Christian, Alexander Setzer, and Martina Eikel. “RoBuSt: A
    Crash-Failure-Resistant Distributed Storage System.” In <i>Proceedings of the
    18th International Conference on Principles of Distributed Systems (OPODIS)</i>,
    107--122. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-14472-6_8">https://doi.org/10.1007/978-3-319-14472-6_8</a>.'
  ieee: 'C. Scheideler, A. Setzer, and M. Eikel, “RoBuSt: A Crash-Failure-Resistant
    Distributed Storage System,” in <i>Proceedings of the 18th International Conference
    on Principles of Distributed Systems (OPODIS)</i>, 2014, pp. 107--122.'
  mla: 'Scheideler, Christian, et al. “RoBuSt: A Crash-Failure-Resistant Distributed
    Storage System.” <i>Proceedings of the 18th International Conference on Principles
    of Distributed Systems (OPODIS)</i>, 2014, pp. 107--122, doi:<a href="https://doi.org/10.1007/978-3-319-14472-6_8">10.1007/978-3-319-14472-6_8</a>.'
  short: 'C. Scheideler, A. Setzer, M. Eikel, in: Proceedings of the 18th International
    Conference on Principles of Distributed Systems (OPODIS), 2014, pp. 107--122.'
date_created: 2017-10-17T12:42:04Z
date_updated: 2022-01-06T06:59:31Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-319-14472-6_8
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T07:16:32Z
  date_updated: 2018-03-20T07:16:32Z
  file_id: '1401'
  file_name: 371-RoBuSt-OPODIS.pdf
  file_size: 269941
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T07:16:32Z
has_accepted_license: '1'
page: 107--122
project:
- _id: '1'
  name: SFB 901
- _id: '13'
  name: SFB 901 - Subprojekt C1
- _id: '4'
  name: SFB 901 - Project Area C
publication: Proceedings of the 18th International Conference on Principles of Distributed
  Systems (OPODIS)
series_title: LNCS
status: public
title: 'RoBuSt: A Crash-Failure-Resistant Distributed Storage System'
type: conference
user_id: '15504'
year: '2014'
...
---
_id: '397'
abstract:
- lang: eng
  text: We present a factor $14D^2$ approximation algorithm for the minimum linear
    arrangement problem on series-parallel graphs, where $D$ is the maximum degree
    in the graph. Given a suitable decomposition of the graph, our algorithm runs
    in time $O(|E|)$ and is very easy to implement. Its divide-and-conquer approach
    allows for an effective parallelization. Note that a suitable decomposition can
    also be computed in time $O(|E|\log{|E|})$ (or even $O(\log{|E|}\log^*{|E|})$
    on an EREW PRAM using $O(|E|)$ processors). For the proof of the approximation
    ratio, we use a sophisticated charging method that uses techniques similar to
    amortized analysis in advanced data structures. On general graphs, the minimum
    linear arrangement problem is known to be NP-hard. To the best of our knowledge,
    the minimum linear arrangement problem on series-parallel graphs has not been
    studied before.
author:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Martina
  full_name: Eikel, Martina
  last_name: Eikel
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Scheideler C, Eikel M, Setzer A. Minimum Linear Arrangement of Series-Parallel
    Graphs. In: <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms
    (WAOA)</i>. LNCS. ; 2014:168--180.'
  apa: Scheideler, C., Eikel, M., &#38; Setzer, A. (2014). Minimum Linear Arrangement
    of Series-Parallel Graphs. In <i>Proceedings of the 12th Workshop on Approximation
    and Online Algorithms (WAOA)</i> (pp. 168--180).
  bibtex: '@inproceedings{Scheideler_Eikel_Setzer_2014, series={LNCS}, title={Minimum
    Linear Arrangement of Series-Parallel Graphs}, booktitle={Proceedings of the 12th
    Workshop on Approximation and Online Algorithms (WAOA)}, author={Scheideler, Christian
    and Eikel, Martina and Setzer, Alexander}, year={2014}, pages={168--180}, collection={LNCS}
    }'
  chicago: Scheideler, Christian, Martina Eikel, and Alexander Setzer. “Minimum Linear
    Arrangement of Series-Parallel Graphs.” In <i>Proceedings of the 12th Workshop
    on Approximation and Online Algorithms (WAOA)</i>, 168--180. LNCS, 2014.
  ieee: C. Scheideler, M. Eikel, and A. Setzer, “Minimum Linear Arrangement of Series-Parallel
    Graphs,” in <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms
    (WAOA)</i>, 2014, pp. 168--180.
  mla: Scheideler, Christian, et al. “Minimum Linear Arrangement of Series-Parallel
    Graphs.” <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms
    (WAOA)</i>, 2014, pp. 168--180.
  short: 'C. Scheideler, M. Eikel, A. Setzer, in: Proceedings of the 12th Workshop
    on Approximation and Online Algorithms (WAOA), 2014, pp. 168--180.'
date_created: 2017-10-17T12:42:09Z
date_updated: 2022-01-06T07:00:02Z
ddc:
- '040'
department:
- _id: '79'
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T06:58:44Z
  date_updated: 2018-03-20T06:58:44Z
  file_id: '1381'
  file_name: 397-WAOA14_01.pdf
  file_size: 365818
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T06:58:44Z
has_accepted_license: '1'
page: 168--180
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 12th Workshop on Approximation and Online Algorithms
  (WAOA)
series_title: LNCS
status: public
title: Minimum Linear Arrangement of Series-Parallel Graphs
type: conference
user_id: '15504'
year: '2014'
...
---
_id: '555'
author:
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: Setzer A. <i>Approximation Algorithms for the Linear Arrangement of Special
    Classes of Graphs</i>. Universität Paderborn; 2013.
  apa: Setzer, A. (2013). <i>Approximation Algorithms for the Linear Arrangement of
    Special Classes of Graphs</i>. Universität Paderborn.
  bibtex: '@book{Setzer_2013, title={Approximation Algorithms for the Linear Arrangement
    of Special Classes of Graphs}, publisher={Universität Paderborn}, author={Setzer,
    Alexander}, year={2013} }'
  chicago: Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement
    of Special Classes of Graphs</i>. Universität Paderborn, 2013.
  ieee: A. Setzer, <i>Approximation Algorithms for the Linear Arrangement of Special
    Classes of Graphs</i>. Universität Paderborn, 2013.
  mla: Setzer, Alexander. <i>Approximation Algorithms for the Linear Arrangement of
    Special Classes of Graphs</i>. Universität Paderborn, 2013.
  short: A. Setzer, Approximation Algorithms for the Linear Arrangement of Special
    Classes of Graphs, Universität Paderborn, 2013.
date_created: 2017-10-17T12:42:40Z
date_updated: 2022-01-06T07:01:59Z
department:
- _id: '79'
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publisher: Universität Paderborn
status: public
title: Approximation Algorithms for the Linear Arrangement of Special Classes of Graphs
type: mastersthesis
user_id: '477'
year: '2013'
...
---
_id: '628'
abstract:
- lang: eng
  text: Network creation games model the creation and usage costs of networks formed
    by a set of selfish peers.Each peer has the ability to change the network in a
    limited way, e.g., by creating or deleting incident links.In doing so, a peer
    can reduce its individual communication cost.Typically, these costs are modeled
    by the maximum or average distance in the network.We introduce a generalized version
    of the basic network creation game (BNCG).In the BNCG (by Alon et al., SPAA 2010),
    each peer may replace one of its incident links by a link to an arbitrary peer.This
    is done in a selfish way in order to minimize either the maximum or average distance
    to all other peers.That is, each peer works towards a network structure that allows
    himself to communicate efficiently with all other peers.However, participants
    of large networks are seldom interested in all peers.Rather, they want to communicate
    efficiently with a small subset only.Our model incorporates these (communication)
    interests explicitly.Given peers with interests and a communication network forming
    a tree, we prove several results on the structure and quality of equilibria in
    our model.We focus on the MAX-version, i.e., each node tries to minimize the maximum
    distance to nodes it is interested in, and give an upper bound of O(\sqrt(n))
    for the private costs in an equilibrium of n peers.Moreover, we give an equilibrium
    for a circular interest graph where a node has private cost Omega(\sqrt(n)), showing
    that our bound is tight.This example can be extended such that we get a tight
    bound of Theta(\sqrt(n)) for the price of anarchy.For the case of general networks
    we show the price of anarchy to be Theta(n).Additionally, we prove an interesting
    connection between a maximum independent set in the interest graph and the private
    costs of the peers.
author:
- first_name: Andreas
  full_name: Cord-Landwehr, Andreas
  last_name: Cord-Landwehr
- first_name: Martina
  full_name: 'Huellmann (married name: Eikel), Martina'
  last_name: 'Huellmann (married name: Eikel)'
- first_name: Peter
  full_name: Kling, Peter
  last_name: Kling
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: 'Cord-Landwehr A, Huellmann (married name: Eikel) M, Kling P, Setzer A. Basic
    Network Creation Games with Communication Interests. In: <i>Proceedings of the
    5th International Symposium on Algorithmic Game Theory (SAGT)</i>. LNCS. ; 2012:72--83.
    doi:<a href="https://doi.org/10.1007/978-3-642-33996-7_7">10.1007/978-3-642-33996-7_7</a>'
  apa: 'Cord-Landwehr, A., Huellmann (married name: Eikel), M., Kling, P., &#38; Setzer,
    A. (2012). Basic Network Creation Games with Communication Interests. In <i>Proceedings
    of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i> (pp.
    72--83). <a href="https://doi.org/10.1007/978-3-642-33996-7_7">https://doi.org/10.1007/978-3-642-33996-7_7</a>'
  bibtex: '@inproceedings{Cord-Landwehr_Huellmann (married name: Eikel)_Kling_Setzer_2012,
    series={LNCS}, title={Basic Network Creation Games with Communication Interests},
    DOI={<a href="https://doi.org/10.1007/978-3-642-33996-7_7">10.1007/978-3-642-33996-7_7</a>},
    booktitle={Proceedings of the 5th International Symposium on Algorithmic Game
    Theory (SAGT)}, author={Cord-Landwehr, Andreas and Huellmann (married name: Eikel),
    Martina and Kling, Peter and Setzer, Alexander}, year={2012}, pages={72--83},
    collection={LNCS} }'
  chicago: 'Cord-Landwehr, Andreas, Martina Huellmann (married name: Eikel), Peter
    Kling, and Alexander Setzer. “Basic Network Creation Games with Communication
    Interests.” In <i>Proceedings of the 5th International Symposium on Algorithmic
    Game Theory (SAGT)</i>, 72--83. LNCS, 2012. <a href="https://doi.org/10.1007/978-3-642-33996-7_7">https://doi.org/10.1007/978-3-642-33996-7_7</a>.'
  ieee: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, and A. Setzer,
    “Basic Network Creation Games with Communication Interests,” in <i>Proceedings
    of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>, 2012,
    pp. 72--83.'
  mla: Cord-Landwehr, Andreas, et al. “Basic Network Creation Games with Communication
    Interests.” <i>Proceedings of the 5th International Symposium on Algorithmic Game
    Theory (SAGT)</i>, 2012, pp. 72--83, doi:<a href="https://doi.org/10.1007/978-3-642-33996-7_7">10.1007/978-3-642-33996-7_7</a>.
  short: 'A. Cord-Landwehr, M. Huellmann (married name: Eikel), P. Kling, A. Setzer,
    in: Proceedings of the 5th International Symposium on Algorithmic Game Theory
    (SAGT), 2012, pp. 72--83.'
date_created: 2017-10-17T12:42:54Z
date_updated: 2022-01-06T07:02:59Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1007/978-3-642-33996-7_7
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T06:42:01Z
  date_updated: 2018-03-15T06:42:01Z
  file_id: '1238'
  file_name: 628-FULL_paper_bncs_with_interests.pdf
  file_size: 300591
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T06:42:01Z
has_accepted_license: '1'
language:
- iso: eng
page: 72--83
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 5th International Symposium on Algorithmic Game Theory
  (SAGT)
series_title: LNCS
status: public
title: Basic Network Creation Games with Communication Interests
type: conference
user_id: '477'
year: '2012'
...
---
_id: '17997'
author:
- first_name: Alexander
  full_name: Setzer, Alexander
  id: '11108'
  last_name: Setzer
citation:
  ama: Setzer A. <i>Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern
    in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn; 2011.
  apa: Setzer, A. (2011). <i>Lokale Online-Strategien zur linearen Anordnung von Teilnehmern
    in einem Peer-to-Peer Netzwerk</i>. Universität Paderborn.
  bibtex: '@book{Setzer_2011, title={Lokale Online-Strategien zur linearen Anordnung
    von Teilnehmern in einem Peer-to-Peer Netzwerk}, publisher={Universität Paderborn},
    author={Setzer, Alexander}, year={2011} }'
  chicago: Setzer, Alexander. <i>Lokale Online-Strategien Zur Linearen Anordnung von
    Teilnehmern in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.
  ieee: A. Setzer, <i>Lokale Online-Strategien zur linearen Anordnung von Teilnehmern
    in einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.
  mla: Setzer, Alexander. <i>Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern
    in Einem Peer-to-Peer Netzwerk</i>. Universität Paderborn, 2011.
  short: A. Setzer, Lokale Online-Strategien Zur Linearen Anordnung von Teilnehmern
    in Einem Peer-to-Peer Netzwerk, Universität Paderborn, 2011.
date_created: 2020-08-17T08:08:13Z
date_updated: 2022-01-06T06:53:24Z
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
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: Lokale Online-Strategien zur linearen Anordnung von Teilnehmern in einem Peer-to-Peer
  Netzwerk
type: bachelorsthesis
user_id: '477'
year: '2011'
...