---
_id: '395'
abstract:
- lang: eng
  text: We consider a multilevel network game, where nodes can improvetheir communication
    costs by connecting to a high-speed network.The n nodes are connected by a static
    network and each node can decideindividually to become a gateway to the high-speed
    network. The goalof a node v is to minimize its private costs, i.e., the sum (SUM-game)
    ormaximum (MAX-game) of communication distances from v to all othernodes plus
    a fixed price α > 0 if it decides to be a gateway. Between gatewaysthe communication
    distance is 0, and gateways also improve othernodes’ distances by behaving as
    shortcuts. For the SUM-game, we showthat for α ≤ n − 1, the price of anarchy is
    Θ (n/√α) and in this rangeequilibria always exist. In range α ∈ (n−1, n(n−1))
    the price of anarchyis Θ(√α), and for α ≥ n(n − 1) it is constant. For the MAX-game,
    weshow that the price of anarchy is either Θ (1 + n/√α), for α ≥ 1, orelse 1.
    Given a graph with girth of at least 4α, equilibria always exist.Concerning the
    dynamics, both games are not potential games. For theSUM-game, we even show that
    it is not weakly acyclic.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Andreas
  full_name: Cord-Landwehr, Andreas
  last_name: Cord-Landwehr
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Alexander
  full_name: Skopalik, Alexander
  id: '40384'
  last_name: Skopalik
citation:
  ama: 'Abshoff S, Cord-Landwehr A, Jung D, Skopalik A. Multilevel Network Games.
    In: <i>Proceedings of the 10th International Conference on Web and Internet Economics
    (WINE)</i>. LNCS. ; 2014:435-440. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>'
  apa: Abshoff, S., Cord-Landwehr, A., Jung, D., &#38; Skopalik, A. (2014). Multilevel
    Network Games. In <i>Proceedings of the 10th International Conference on Web and
    Internet Economics (WINE)</i> (pp. 435–440). <a href="https://doi.org/10.1007/978-3-319-13129-0_36">https://doi.org/10.1007/978-3-319-13129-0_36</a>
  bibtex: '@inproceedings{Abshoff_Cord-Landwehr_Jung_Skopalik_2014, series={LNCS},
    title={Multilevel Network Games}, DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>},
    booktitle={Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)}, author={Abshoff, Sebastian and Cord-Landwehr, Andreas and Jung,
    Daniel and Skopalik, Alexander}, year={2014}, pages={435–440}, collection={LNCS}
    }'
  chicago: Abshoff, Sebastian, Andreas Cord-Landwehr, Daniel Jung, and Alexander Skopalik.
    “Multilevel Network Games.” In <i>Proceedings of the 10th International Conference
    on Web and Internet Economics (WINE)</i>, 435–40. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_36">https://doi.org/10.1007/978-3-319-13129-0_36</a>.
  ieee: S. Abshoff, A. Cord-Landwehr, D. Jung, and A. Skopalik, “Multilevel Network
    Games,” in <i>Proceedings of the 10th International Conference on Web and Internet
    Economics (WINE)</i>, 2014, pp. 435–440.
  mla: Abshoff, Sebastian, et al. “Multilevel Network Games.” <i>Proceedings of the
    10th International Conference on Web and Internet Economics (WINE)</i>, 2014,
    pp. 435–40, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_36">10.1007/978-3-319-13129-0_36</a>.
  short: 'S. Abshoff, A. Cord-Landwehr, D. Jung, A. Skopalik, in: Proceedings of the
    10th International Conference on Web and Internet Economics (WINE), 2014, pp.
    435–440.'
date_created: 2017-10-17T12:42:09Z
date_updated: 2022-01-06T06:59:59Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-319-13129-0_36
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-20T06:59:20Z
  date_updated: 2018-03-20T06:59:20Z
  file_id: '1382'
  file_name: 395-WINE2014ACJS.pdf
  file_size: 161479
  relation: main_file
  success: 1
file_date_updated: 2018-03-20T06:59:20Z
has_accepted_license: '1'
language:
- iso: eng
page: 435-440
project:
- _id: '1'
  name: SFB 901
- _id: '7'
  name: SFB 901 - Subprojekt A3
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Proceedings of the 10th International Conference on Web and Internet
  Economics (WINE)
series_title: LNCS
status: public
title: Multilevel Network Games
type: conference
user_id: '15415'
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: '412'
abstract:
- lang: eng
  text: In this paper we present and analyze HSkip+, a self-stabilizing overlay network
    for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology
    as the Skip+ graph proposed by Jacob et al. [PODC 2009] but its self-stabilization
    mechanism significantly outperforms the self-stabilization mechanism proposed
    for Skip+. Also, the nodes are now ordered according to their bandwidths and not
    according to their identifiers. Various other solutions have already been proposed
    for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing.
    In addition to HSkip+ being self-stabilizing, its performance is on par with the
    best previous bounds on the time and work for joining or leaving a network of
    peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation
    and congestion for routing messages is on par with the best previous bounds for
    such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical
    investigations are backed by simulations demonstrating that HSkip+ is indeed performing
    much better than Skip+ and working correctly under high churn rates.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Kalman
  full_name: Graffi, Kalman
  last_name: Graffi
citation:
  ama: 'Feldotto M, Scheideler C, Graffi K. HSkip+: A Self-Stabilizing Overlay Network
    for Nodes with Heterogeneous Bandwidths. In: <i>Proceedings of the 14th IEEE International
    Conference on Peer-to-Peer Computing (P2P)</i>. ; 2014:1-10. doi:<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>'
  apa: 'Feldotto, M., Scheideler, C., &#38; Graffi, K. (2014). HSkip+: A Self-Stabilizing
    Overlay Network for Nodes with Heterogeneous Bandwidths. In <i>Proceedings of
    the 14th IEEE International Conference on Peer-to-Peer Computing (P2P)</i> (pp.
    1–10). <a href="https://doi.org/10.1109/P2P.2014.6934300">https://doi.org/10.1109/P2P.2014.6934300</a>'
  bibtex: '@inproceedings{Feldotto_Scheideler_Graffi_2014, title={HSkip+: A Self-Stabilizing
    Overlay Network for Nodes with Heterogeneous Bandwidths}, DOI={<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>},
    booktitle={Proceedings of the 14th IEEE International Conference on Peer-to-Peer
    Computing (P2P)}, author={Feldotto, Matthias and Scheideler, Christian and Graffi,
    Kalman}, year={2014}, pages={1–10} }'
  chicago: 'Feldotto, Matthias, Christian Scheideler, and Kalman Graffi. “HSkip+:
    A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths.” In
    <i>Proceedings of the 14th IEEE International Conference on Peer-to-Peer Computing
    (P2P)</i>, 1–10, 2014. <a href="https://doi.org/10.1109/P2P.2014.6934300">https://doi.org/10.1109/P2P.2014.6934300</a>.'
  ieee: 'M. Feldotto, C. Scheideler, and K. Graffi, “HSkip+: A Self-Stabilizing Overlay
    Network for Nodes with Heterogeneous Bandwidths,” in <i>Proceedings of the 14th
    IEEE International Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10.'
  mla: 'Feldotto, Matthias, et al. “HSkip+: A Self-Stabilizing Overlay Network for
    Nodes with Heterogeneous Bandwidths.” <i>Proceedings of the 14th IEEE International
    Conference on Peer-to-Peer Computing (P2P)</i>, 2014, pp. 1–10, doi:<a href="https://doi.org/10.1109/P2P.2014.6934300">10.1109/P2P.2014.6934300</a>.'
  short: 'M. Feldotto, C. Scheideler, K. Graffi, in: Proceedings of the 14th IEEE
    International Conference on Peer-to-Peer Computing (P2P), 2014, pp. 1–10.'
date_created: 2017-10-17T12:42:12Z
date_updated: 2022-01-06T07:00:20Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
- _id: '541'
doi: 10.1109/P2P.2014.6934300
external_id:
  arxiv:
  - '1408.0395'
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-16T11:34:00Z
  date_updated: 2018-03-16T11:34:00Z
  file_id: '1361'
  file_name: 412-FSG2014P2P.pdf
  file_size: 472321
  relation: main_file
  success: 1
file_date_updated: 2018-03-16T11:34:00Z
has_accepted_license: '1'
page: 1-10
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 14th IEEE International Conference on Peer-to-Peer
  Computing (P2P)
status: public
title: 'HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths'
type: conference
user_id: '14052'
year: '2014'
...
---
_id: '434'
author:
- first_name: Linghui
  full_name: Luo, Linghui
  last_name: Luo
citation:
  ama: Luo L. <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem
    in Skip+ Graphen</i>. Universität Paderborn; 2014.
  apa: Luo, L. (2014). <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep
    Problem in Skip+ Graphen</i>. Universität Paderborn.
  bibtex: '@book{Luo_2014, title={Ein selbst-stabilisierender Algorithmus für das
    Finite Sleep Problem in Skip+ Graphen}, publisher={Universität Paderborn}, author={Luo,
    Linghui}, year={2014} }'
  chicago: Luo, Linghui. <i>Ein selbst-stabilisierender Algorithmus für das Finite
    Sleep Problem in Skip+ Graphen</i>. Universität Paderborn, 2014.
  ieee: L. Luo, <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem
    in Skip+ Graphen</i>. Universität Paderborn, 2014.
  mla: Luo, Linghui. <i>Ein selbst-stabilisierender Algorithmus für das Finite Sleep
    Problem in Skip+ Graphen</i>. Universität Paderborn, 2014.
  short: L. Luo, Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem
    in Skip+ Graphen, Universität Paderborn, 2014.
date_created: 2017-10-17T12:42:16Z
date_updated: 2022-01-06T07:00:57Z
language:
- iso: ger
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: Ein selbst-stabilisierender Algorithmus für das Finite Sleep Problem in Skip+
  Graphen
type: bachelorsthesis
user_id: '477'
year: '2014'
...
---
_id: '18000'
author:
- first_name: Fritz
  full_name: Blumentritt, Fritz
  last_name: Blumentritt
citation:
  ama: Blumentritt F. <i>Cliquenbildung in Verteilten Systemen</i>. Universität Paderborn;
    2013.
  apa: Blumentritt, F. (2013). <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn.
  bibtex: '@book{Blumentritt_2013, title={Cliquenbildung in verteilten Systemen},
    publisher={Universität Paderborn}, author={Blumentritt, Fritz}, year={2013} }'
  chicago: Blumentritt, Fritz. <i>Cliquenbildung in Verteilten Systemen</i>. Universität
    Paderborn, 2013.
  ieee: F. Blumentritt, <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn, 2013.
  mla: Blumentritt, Fritz. <i>Cliquenbildung in Verteilten Systemen</i>. Universität
    Paderborn, 2013.
  short: F. Blumentritt, Cliquenbildung in Verteilten Systemen, Universität Paderborn,
    2013.
date_created: 2020-08-17T08:14:17Z
date_updated: 2022-01-06T06:53:25Z
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: Cliquenbildung in verteilten Systemen
type: bachelorsthesis
user_id: '477'
year: '2013'
...
---
_id: '476'
abstract:
- lang: eng
  text: 'An elementary h-route ow, for an integer h 1, is a set of h edge- disjoint
    paths between a source and a sink, each path carrying a unit of ow, and an h-route
    ow is a non-negative linear combination of elementary h-routeows. An h-route cut
    is a set of edges whose removal decreases the maximum h-route ow between a given
    source-sink pair (or between every source-sink pair in the multicommodity setting)
    to zero. The main result of this paper is an approximate duality theorem for multicommodity
    h-route cuts and ows, for h 3: The size of a minimum h-route cut is at least f=h
    and at most O(log4 k f) where f is the size of the maximum h-routeow and k is
    the number of commodities. The main step towards the proof of this duality is
    the design and analysis of a polynomial-time approximation algorithm for the minimum
    h-route cut problem for h = 3 that has an approximation ratio of O(log4 k). Previously,
    polylogarithmic approximation was known only for h-route cuts for h 2. A key ingredient
    of our algorithm is a novel rounding technique that we call multilevel ball-growing.
    Though the proof of the duality relies on this algorithm, it is not a straightforward
    corollary of it as in the case of classical multicommodity ows and cuts. Similar
    results are shown also for the sparsest multiroute cut problem.'
author:
- first_name: Petr
  full_name: Kolman, Petr
  last_name: Kolman
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  ama: 'Kolman P, Scheideler C. Towards Duality of Multicommodity Multiroute Cuts
    and Flows: Multilevel Ball-Growing. <i>Theory of Computing Systems</i>. 2013;(2):341-363.
    doi:<a href="https://doi.org/10.1007/s00224-013-9454-3">10.1007/s00224-013-9454-3</a>'
  apa: 'Kolman, P., &#38; Scheideler, C. (2013). Towards Duality of Multicommodity
    Multiroute Cuts and Flows: Multilevel Ball-Growing. <i>Theory of Computing Systems</i>,
    (2), 341–363. <a href="https://doi.org/10.1007/s00224-013-9454-3">https://doi.org/10.1007/s00224-013-9454-3</a>'
  bibtex: '@article{Kolman_Scheideler_2013, title={Towards Duality of Multicommodity
    Multiroute Cuts and Flows: Multilevel Ball-Growing}, DOI={<a href="https://doi.org/10.1007/s00224-013-9454-3">10.1007/s00224-013-9454-3</a>},
    number={2}, journal={Theory of Computing Systems}, publisher={Springer}, author={Kolman,
    Petr and Scheideler, Christian}, year={2013}, pages={341–363} }'
  chicago: 'Kolman, Petr, and Christian Scheideler. “Towards Duality of Multicommodity
    Multiroute Cuts and Flows: Multilevel Ball-Growing.” <i>Theory of Computing Systems</i>,
    no. 2 (2013): 341–63. <a href="https://doi.org/10.1007/s00224-013-9454-3">https://doi.org/10.1007/s00224-013-9454-3</a>.'
  ieee: 'P. Kolman and C. Scheideler, “Towards Duality of Multicommodity Multiroute
    Cuts and Flows: Multilevel Ball-Growing,” <i>Theory of Computing Systems</i>,
    no. 2, pp. 341–363, 2013.'
  mla: 'Kolman, Petr, and Christian Scheideler. “Towards Duality of Multicommodity
    Multiroute Cuts and Flows: Multilevel Ball-Growing.” <i>Theory of Computing Systems</i>,
    no. 2, Springer, 2013, pp. 341–63, doi:<a href="https://doi.org/10.1007/s00224-013-9454-3">10.1007/s00224-013-9454-3</a>.'
  short: P. Kolman, C. Scheideler, Theory of Computing Systems (2013) 341–363.
date_created: 2017-10-17T12:42:24Z
date_updated: 2022-01-06T07:01:21Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/s00224-013-9454-3
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T14:07:18Z
  date_updated: 2018-03-15T14:07:18Z
  file_id: '1326'
  file_name: 476-tocsrevised3b.pdf
  file_size: 264308
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T14:07:18Z
has_accepted_license: '1'
issue: '2'
page: 341-363
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Theory of Computing Systems
publisher: Springer
status: public
title: 'Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing'
type: journal_article
user_id: '477'
year: '2013'
...
---
_id: '477'
abstract:
- lang: eng
  text: We consider the k-token dissemination problem, where k initially arbitrarily
    distributed tokens have to be disseminated to all nodes in a dynamic network (as
    introduced by Kuhn et al., STOC 2010). In contrast to general dynamic networks,
    our dynamic networks are unit disk graphs, i.e., nodes are embedded into the Euclidean
    plane and two nodes are connected if and only if their distance is at most R.
    Our worst-case adversary is allowed to move the nodes on the plane, but the maximum
    velocity v_max of each node is limited and the graph must be connected in each
    round. For this model, we provide almost tight lower and upper bounds for k-token
    dissemination if nodes are restricted to send only one token per round. It turns
    out that the maximum velocity v_max is a meaningful parameter to characterize
    dynamics in our model.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Markus
  full_name: Benter, Markus
  last_name: Benter
- first_name: Andreas
  full_name: Cord-Landwehr, Andreas
  last_name: Cord-Landwehr
- first_name: Manuel
  full_name: Malatyali, Manuel
  last_name: Malatyali
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Abshoff S, Benter M, Cord-Landwehr A, Malatyali M, Meyer auf der Heide F.
    Token Dissemination in Geometric Dynamic Networks. In: <i>Algorithms for Sensor
    Systems - 9th International Symposium on Algorithms and Experiments for Sensor
    Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013, Sophia
    Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>. Lecture Notes
    in Computer Science. ; 2013:22-34. doi:<a href="https://doi.org/10.1007/978-3-642-45346-5_3">10.1007/978-3-642-45346-5_3</a>'
  apa: Abshoff, S., Benter, M., Cord-Landwehr, A., Malatyali, M., &#38; Meyer auf
    der Heide, F. (2013). Token Dissemination in Geometric Dynamic Networks. In <i>Algorithms
    for Sensor Systems - 9th International Symposium on Algorithms and Experiments
    for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS}
    2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>
    (pp. 22–34). <a href="https://doi.org/10.1007/978-3-642-45346-5_3">https://doi.org/10.1007/978-3-642-45346-5_3</a>
  bibtex: '@inproceedings{Abshoff_Benter_Cord-Landwehr_Malatyali_Meyer auf der Heide_2013,
    series={Lecture Notes in Computer Science}, title={Token Dissemination in Geometric
    Dynamic Networks}, DOI={<a href="https://doi.org/10.1007/978-3-642-45346-5_3">10.1007/978-3-642-45346-5_3</a>},
    booktitle={Algorithms for Sensor Systems - 9th International Symposium on Algorithms
    and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics,
    {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected
    Papers}, author={Abshoff, Sebastian and Benter, Markus and Cord-Landwehr, Andreas
    and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={22–34},
    collection={Lecture Notes in Computer Science} }'
  chicago: Abshoff, Sebastian, Markus Benter, Andreas Cord-Landwehr, Manuel Malatyali,
    and Friedhelm Meyer auf der Heide. “Token Dissemination in Geometric Dynamic Networks.”
    In <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms
    and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics,
    {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected
    Papers</i>, 22–34. Lecture Notes in Computer Science, 2013. <a href="https://doi.org/10.1007/978-3-642-45346-5_3">https://doi.org/10.1007/978-3-642-45346-5_3</a>.
  ieee: S. Abshoff, M. Benter, A. Cord-Landwehr, M. Malatyali, and F. Meyer auf der
    Heide, “Token Dissemination in Geometric Dynamic Networks,” in <i>Algorithms for
    Sensor Systems - 9th International Symposium on Algorithms and Experiments for
    Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS} 2013,
    Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>, 2013,
    pp. 22–34.
  mla: Abshoff, Sebastian, et al. “Token Dissemination in Geometric Dynamic Networks.”
    <i>Algorithms for Sensor Systems - 9th International Symposium on Algorithms and
    Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, {ALGOSENSORS}
    2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected Papers</i>,
    2013, pp. 22–34, doi:<a href="https://doi.org/10.1007/978-3-642-45346-5_3">10.1007/978-3-642-45346-5_3</a>.
  short: 'S. Abshoff, M. Benter, A. Cord-Landwehr, M. Malatyali, F. Meyer auf der
    Heide, in: Algorithms for Sensor Systems - 9th International Symposium on Algorithms
    and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics,
    {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected
    Papers, 2013, pp. 22–34.'
date_created: 2017-10-17T12:42:25Z
date_updated: 2022-01-06T07:01:21Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-45346-5_3
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T14:06:38Z
  date_updated: 2018-03-15T14:06:38Z
  file_id: '1325'
  file_name: 477-geometric-dynamic-networks_01.pdf
  file_size: 193169
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T14:06:38Z
has_accepted_license: '1'
page: 22-34
project:
- _id: '1'
  name: SFB 901
- _id: '5'
  name: SFB 901 - Subprojekt A1
- _id: '2'
  name: SFB 901 - Project Area A
publication: Algorithms for Sensor Systems - 9th International Symposium on Algorithms
  and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics,
  {ALGOSENSORS} 2013, Sophia Antipolis, France, September 5-6, 2013, Revised Selected
  Papers
series_title: Lecture Notes in Computer Science
status: public
title: Token Dissemination in Geometric Dynamic Networks
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '481'
abstract:
- lang: eng
  text: Cloud computing offers high availability, dynamic scalability, and elasticity
    requiring only very little administration. However, this service comes with financial
    costs. Peer-to-peer systems, in contrast, operate at very low costs but cannot
    match the quality of service of the cloud. This paper focuses on the case study
    of Wikipedia and presents an approach to reduce the operational costs of hosting
    similar websites in the cloud by using a practical peer-to-peer approach. The
    visitors of the site are joining a Chord overlay, which acts as first cache for
    article lookups. Simulation results show, that up to 72% of the article lookups
    in Wikipedia could be answered by other visitors instead of using the cloud.
author:
- first_name: Kalman
  full_name: Graffi, Kalman
  last_name: Graffi
- first_name: Lars
  full_name: Bremer, Lars
  last_name: Bremer
citation:
  ama: 'Graffi K, Bremer L. Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia
    Case. In: <i>Proceedings of the International Conference on Communications (ICC’13)</i>.
    ; 2013:3444-3449. doi:<a href="https://doi.org/10.1109/ICC.2013.6655082">10.1109/ICC.2013.6655082</a>'
  apa: 'Graffi, K., &#38; Bremer, L. (2013). Symbiotic Coupling of P2P and Cloud Systems:
    The Wikipedia Case. In <i>Proceedings of the International Conference on Communications
    (ICC’13)</i> (pp. 3444–3449). <a href="https://doi.org/10.1109/ICC.2013.6655082">https://doi.org/10.1109/ICC.2013.6655082</a>'
  bibtex: '@inproceedings{Graffi_Bremer_2013, title={Symbiotic Coupling of P2P and
    Cloud Systems: The Wikipedia Case}, DOI={<a href="https://doi.org/10.1109/ICC.2013.6655082">10.1109/ICC.2013.6655082</a>},
    booktitle={Proceedings of the International Conference on Communications (ICC’13)},
    author={Graffi, Kalman and Bremer, Lars}, year={2013}, pages={3444–3449} }'
  chicago: 'Graffi, Kalman, and Lars Bremer. “Symbiotic Coupling of P2P and Cloud
    Systems: The Wikipedia Case.” In <i>Proceedings of the International Conference
    on Communications (ICC’13)</i>, 3444–49, 2013. <a href="https://doi.org/10.1109/ICC.2013.6655082">https://doi.org/10.1109/ICC.2013.6655082</a>.'
  ieee: 'K. Graffi and L. Bremer, “Symbiotic Coupling of P2P and Cloud Systems: The
    Wikipedia Case,” in <i>Proceedings of the International Conference on Communications
    (ICC’13)</i>, 2013, pp. 3444–3449.'
  mla: 'Graffi, Kalman, and Lars Bremer. “Symbiotic Coupling of P2P and Cloud Systems:
    The Wikipedia Case.” <i>Proceedings of the International Conference on Communications
    (ICC’13)</i>, 2013, pp. 3444–49, doi:<a href="https://doi.org/10.1109/ICC.2013.6655082">10.1109/ICC.2013.6655082</a>.'
  short: 'K. Graffi, L. Bremer, in: Proceedings of the International Conference on
    Communications (ICC’13), 2013, pp. 3444–3449.'
date_created: 2017-10-17T12:42:26Z
date_updated: 2022-01-06T07:01:25Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/ICC.2013.6655082
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T14:02:01Z
  date_updated: 2018-03-15T14:02:01Z
  file_id: '1321'
  file_name: 481-Symbiotic.Coupling.of.P2P.and.Cloud.Systems.The.Wikipedia.Case2.pdf
  file_size: 1405789
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T14:02:01Z
has_accepted_license: '1'
language:
- iso: eng
page: '3444 - 3449 '
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 International Conference on Communications (ICC'13)
status: public
title: 'Symbiotic Coupling of P2P and Cloud Systems: The Wikipedia Case'
type: conference
user_id: '477'
year: '2013'
...
---
_id: '503'
author:
- first_name: Andreas
  full_name: Blix, Andreas
  last_name: Blix
citation:
  ama: Blix A. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität
    Paderborn; 2013.
  apa: Blix, A. (2013). <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität
    Paderborn.
  bibtex: '@book{Blix_2013, title={Optimale und adaptive binäre Bäume in Netzwerken},
    publisher={Universität Paderborn}, author={Blix, Andreas}, year={2013} }'
  chicago: Blix, Andreas. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>.
    Universität Paderborn, 2013.
  ieee: A. Blix, <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität
    Paderborn, 2013.
  mla: Blix, Andreas. <i>Optimale und adaptive binäre Bäume in Netzwerken</i>. Universität
    Paderborn, 2013.
  short: A. Blix, Optimale und adaptive binäre Bäume in Netzwerken, Universität Paderborn,
    2013.
date_created: 2017-10-17T12:42:30Z
date_updated: 2022-01-06T07:01:35Z
language:
- iso: ger
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: Optimale und adaptive binäre Bäume in Netzwerken
type: bachelorsthesis
user_id: '477'
year: '2013'
...
---
_id: '507'
abstract:
- lang: eng
  text: We study two-party communication in the context of directed dynamic networks
    that are controlled by an adaptive adversary. This adversary is able to change
    all edges as long as the networks stay strongly-connected in each round. In this
    work, we establish a relation between counting the total number of nodes in the
    network and the problem of exchanging tokens between two communication partners
    which communicate through a dynamic network. We show that the communication problem
    for a constant fraction of n tokens in a dynamic network with n nodes is at most
    as hard as counting the number of nodes in a dynamic network with at most 4n+3
    nodes. For the proof, we construct a family of directed dynamic networks and apply
    a lower bound from two-party communication complexity.
author:
- first_name: Sebastian
  full_name: Abshoff, Sebastian
  last_name: Abshoff
- first_name: Markus
  full_name: Benter, Markus
  last_name: Benter
- first_name: Manuel
  full_name: Malatyali, Manuel
  last_name: Malatyali
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Abshoff S, Benter M, Malatyali M, Meyer auf der Heide F. On Two-Party Communication
    Through Dynamic Networks. In: <i>Proceedings of the 17th International Conference
    on Principles of Distributed Systems (OPODIS)</i>. LNCS. ; 2013:11-22. doi:<a
    href="https://doi.org/10.1007/978-3-319-03850-6_2">10.1007/978-3-319-03850-6_2</a>'
  apa: Abshoff, S., Benter, M., Malatyali, M., &#38; Meyer auf der Heide, F. (2013).
    On Two-Party Communication Through Dynamic Networks. In <i>Proceedings of the
    17th International Conference on Principles of Distributed Systems (OPODIS)</i>
    (pp. 11–22). <a href="https://doi.org/10.1007/978-3-319-03850-6_2">https://doi.org/10.1007/978-3-319-03850-6_2</a>
  bibtex: '@inproceedings{Abshoff_Benter_Malatyali_Meyer auf der Heide_2013, series={LNCS},
    title={On Two-Party Communication Through Dynamic Networks}, DOI={<a href="https://doi.org/10.1007/978-3-319-03850-6_2">10.1007/978-3-319-03850-6_2</a>},
    booktitle={Proceedings of the 17th International Conference on Principles of Distributed
    Systems (OPODIS)}, author={Abshoff, Sebastian and Benter, Markus and Malatyali,
    Manuel and Meyer auf der Heide, Friedhelm}, year={2013}, pages={11–22}, collection={LNCS}
    }'
  chicago: Abshoff, Sebastian, Markus Benter, Manuel Malatyali, and Friedhelm Meyer
    auf der Heide. “On Two-Party Communication Through Dynamic Networks.” In <i>Proceedings
    of the 17th International Conference on Principles of Distributed Systems (OPODIS)</i>,
    11–22. LNCS, 2013. <a href="https://doi.org/10.1007/978-3-319-03850-6_2">https://doi.org/10.1007/978-3-319-03850-6_2</a>.
  ieee: S. Abshoff, M. Benter, M. Malatyali, and F. Meyer auf der Heide, “On Two-Party
    Communication Through Dynamic Networks,” in <i>Proceedings of the 17th International
    Conference on Principles of Distributed Systems (OPODIS)</i>, 2013, pp. 11–22.
  mla: Abshoff, Sebastian, et al. “On Two-Party Communication Through Dynamic Networks.”
    <i>Proceedings of the 17th International Conference on Principles of Distributed
    Systems (OPODIS)</i>, 2013, pp. 11–22, doi:<a href="https://doi.org/10.1007/978-3-319-03850-6_2">10.1007/978-3-319-03850-6_2</a>.
  short: 'S. Abshoff, M. Benter, M. Malatyali, F. Meyer auf der Heide, in: Proceedings
    of the 17th International Conference on Principles of Distributed Systems (OPODIS),
    2013, pp. 11–22.'
date_created: 2017-10-17T12:42:31Z
date_updated: 2022-01-06T07:01:36Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-319-03850-6_2
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:47:31Z
  date_updated: 2018-03-15T10:47:31Z
  file_id: '1305'
  file_name: 507-on-two-party-communication-through-dynamic-networks_01.pdf
  file_size: 181398
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:47:31Z
has_accepted_license: '1'
page: 11-22
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 17th International Conference on Principles of Distributed
  Systems (OPODIS)
series_title: LNCS
status: public
title: On Two-Party Communication Through Dynamic Networks
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '510'
author:
- first_name: Chintan
  full_name: Jayesh Parekh, Chintan
  last_name: Jayesh Parekh
citation:
  ama: Jayesh Parekh C. <i>Meta-Data Based Search in Structured Peer-to-Peer Networks</i>.
    Universität Paderborn; 2013.
  apa: Jayesh Parekh, C. (2013). <i>Meta-data based Search in Structured Peer-to-Peer
    Networks</i>. Universität Paderborn.
  bibtex: '@book{Jayesh Parekh_2013, title={Meta-data based Search in Structured Peer-to-Peer
    Networks}, publisher={Universität Paderborn}, author={Jayesh Parekh, Chintan},
    year={2013} }'
  chicago: Jayesh Parekh, Chintan. <i>Meta-Data Based Search in Structured Peer-to-Peer
    Networks</i>. Universität Paderborn, 2013.
  ieee: C. Jayesh Parekh, <i>Meta-data based Search in Structured Peer-to-Peer Networks</i>.
    Universität Paderborn, 2013.
  mla: Jayesh Parekh, Chintan. <i>Meta-Data Based Search in Structured Peer-to-Peer
    Networks</i>. Universität Paderborn, 2013.
  short: C. Jayesh Parekh, Meta-Data Based Search in Structured Peer-to-Peer Networks,
    Universität Paderborn, 2013.
date_created: 2017-10-17T12:42:31Z
date_updated: 2022-01-06T07:01:37Z
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: Meta-data based Search in Structured Peer-to-Peer Networks
type: mastersthesis
user_id: '15504'
year: '2013'
...
---
_id: '513'
abstract:
- lang: eng
  text: This paper initiates the study of self-adjusting networks (or distributed
    data structures) whose topologies dynamically adapt to a communication pattern
    $\sigma$. We present a fully decentralized self-adjusting solution called SplayNet.
    A SplayNet is a distributed generalization of the classic splay tree concept.
    It ensures short paths (which can be found using local-greedy routing) between
    communication partners while minimizing topological rearrangements. We derive
    an upper bound for the amortized communication cost of a SplayNet based on empirical
    entropies of $\sigma$, and show that SplayNets have several interesting convergence
    properties. For instance, SplayNets features a provable online optimality under
    special requests scenarios. We also investigate the optimal static network and
    prove different lower bounds for the average communication cost based on graph
    cuts and on the empirical entropy of the communication pattern $\sigma$. From
    these lower bounds it follows, e.g., that SplayNets are optimal in scenarios where
    the requests follow a product distribution as well. Finally, this paper shows
    that in contrast to the Minimum Linear Arrangement problem which is generally
    NP-hard, the optimal static tree network can be computed in polynomial time for
    any guest graph, despite the exponentially large graph family. We complement our
    formal analysis with a small simulation study on a Facebook graph.
author:
- first_name: Chen
  full_name: Avin, Chen
  last_name: Avin
- first_name: Bernhard
  full_name: Häupler, Bernhard
  last_name: Häupler
- first_name: Zvi
  full_name: Lotker, Zvi
  last_name: Lotker
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Avin C, Häupler B, Lotker Z, Scheideler C, Schmid S. Locally Self-Adjusting
    Tree Networks. In: <i>Proceedings of the 27th IEEE International Parallel and
    Distributed Processing Symposium (IPDPS)</i>. ; 2013:395-406. doi:<a href="https://doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>'
  apa: Avin, C., Häupler, B., Lotker, Z., Scheideler, C., &#38; Schmid, S. (2013).
    Locally Self-Adjusting Tree Networks. In <i>Proceedings of the 27th IEEE International
    Parallel and Distributed Processing Symposium (IPDPS)</i> (pp. 395–406). <a href="https://doi.org/10.1109/IPDPS.2013.40">https://doi.org/10.1109/IPDPS.2013.40</a>
  bibtex: '@inproceedings{Avin_Häupler_Lotker_Scheideler_Schmid_2013, title={Locally
    Self-Adjusting Tree Networks}, DOI={<a href="https://doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>},
    booktitle={Proceedings of the 27th IEEE International Parallel and Distributed
    Processing Symposium (IPDPS)}, author={Avin, Chen and Häupler, Bernhard and Lotker,
    Zvi and Scheideler, Christian and Schmid, Stefan}, year={2013}, pages={395–406}
    }'
  chicago: Avin, Chen, Bernhard Häupler, Zvi Lotker, Christian Scheideler, and Stefan
    Schmid. “Locally Self-Adjusting Tree Networks.” In <i>Proceedings of the 27th
    IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>,
    395–406, 2013. <a href="https://doi.org/10.1109/IPDPS.2013.40">https://doi.org/10.1109/IPDPS.2013.40</a>.
  ieee: C. Avin, B. Häupler, Z. Lotker, C. Scheideler, and S. Schmid, “Locally Self-Adjusting
    Tree Networks,” in <i>Proceedings of the 27th IEEE International Parallel and
    Distributed Processing Symposium (IPDPS)</i>, 2013, pp. 395–406.
  mla: Avin, Chen, et al. “Locally Self-Adjusting Tree Networks.” <i>Proceedings of
    the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS)</i>,
    2013, pp. 395–406, doi:<a href="https://doi.org/10.1109/IPDPS.2013.40">10.1109/IPDPS.2013.40</a>.
  short: 'C. Avin, B. Häupler, Z. Lotker, C. Scheideler, S. Schmid, in: Proceedings
    of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
    2013, pp. 395–406.'
date_created: 2017-10-17T12:42:32Z
date_updated: 2022-01-06T07:01:38Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/IPDPS.2013.40
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:45:15Z
  date_updated: 2018-03-15T10:45:15Z
  file_id: '1303'
  file_name: 513-ipdps13_01.pdf
  file_size: 518804
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:45:15Z
has_accepted_license: '1'
page: 395-406
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 27th IEEE International Parallel and Distributed Processing
  Symposium (IPDPS)
status: public
title: Locally Self-Adjusting Tree Networks
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '514'
abstract:
- lang: eng
  text: Diese Arbeit besch{\"a}ftigt sich mit dem Facility Location Problem. Dies
    ist ein Optimierungsproblem, bei dem festgelegt werden muss an welchen Positionen
    Ressourcen zur Verf{\"u}gung gestellt werden, so dass diese von Nutzern gut erreicht
    werden k{\"o}nnen. Es sollen dabei Kosten minimiert werden, die zum einen durch
    Bereitstellung von Ressourcen und zum anderen durch Verbindungskosten zwischen
    Nutzern und Ressourcen entstehen. Die Schwierigkeit des Problems liegt darin,
    dass man einerseits m{\"o}glichst wenige Ressourcen zur Verf{\"u}gung stellen
    m{\"o}chte, andererseits daf{\"u}r sorgen muss, dass sich Nutzer nicht all zu
    weit weg von Ressourcen befinden. Dies w{\"u}rde n{\"a}mlich hohe Verbindungskosten
    nach sich ziehen. Das Facility Location Problem wurde bereits sehr intensiv in
    vielen unterschiedlichen Varianten untersucht. In dieser Arbeit werden drei Varianten
    des Problems modelliert und neue Algorithmen f{\"u}r sie entwickelt und bez{\"u}glich
    ihres Approximationsfaktors und ihrer Laufzeit analysiert. Jede dieser drei untersuchten
    Varianten hat einen besonderen Schwerpunkt. Bei der ersten Varianten handelt es
    sich um ein Online Problem, da hier die Eingabe nicht von Anfang an bekannt ist,
    sondern Schritt f{\"u}r Schritt enth{\"u}llt wird. Die Schwierigkeit hierbei besteht
    darin unwiderrufliche Entscheidungen treffen zu m{\"u}ssen ohne dabei die Zukunft
    zu kennen und trotzdem eine zu jeder Zeit gute L{\"o}sung angeben zu k{\"o}nnen.
    Der Schwerpunkt der zweiten Variante liegt auf Lokalit{\"a}t, die z.B. in Sensornetzwerken
    von großer Bedeutung ist. Hier soll eine L{\"o}sung verteilt und nur mit Hilfe
    von lokalen Information berechnet werden. Schließlich besch{\"a}ftigt sich die
    dritte Variante mit einer verteilten Berechnung, bei welcher nur eine stark beschr{\"a}nkte
    Datenmenge verschickt werden darf und dabei trotzdem ein sehr guter Approximationsfaktor
    erreicht werden muss. Die bei der Analyse der Approximationsfaktoren bzw. der
    Kompetitivit{\"a}t verwendeten Techniken basieren zum großen Teil auf Absch{\"a}tzung
    der primalen L{\"o}sung mit Hilfe einer L{\"o}sung des zugeh{\"o}rigen dualen
    Problems. F{\"u}r die Modellierung von Lokalit{\"a}t wird das weitverbreitete
    LOCAL Modell verwendet. In diesem Modell werden f{\"u}r die Algorithmen subpolynomielle
    obere Laufzeitschranken gezeigt.
author:
- first_name: Peter
  full_name: Pietrzyk, Peter
  last_name: Pietrzyk
citation:
  ama: Pietrzyk P. <i>Local and Online Algorithms for Facility Location</i>. Universität
    Paderborn; 2013.
  apa: Pietrzyk, P. (2013). <i>Local and Online Algorithms for Facility Location</i>.
    Universität Paderborn.
  bibtex: '@book{Pietrzyk_2013, title={Local and Online Algorithms for Facility Location},
    publisher={Universität Paderborn}, author={Pietrzyk, Peter}, year={2013} }'
  chicago: Pietrzyk, Peter. <i>Local and Online Algorithms for Facility Location</i>.
    Universität Paderborn, 2013.
  ieee: P. Pietrzyk, <i>Local and Online Algorithms for Facility Location</i>. Universität
    Paderborn, 2013.
  mla: Pietrzyk, Peter. <i>Local and Online Algorithms for Facility Location</i>.
    Universität Paderborn, 2013.
  short: P. Pietrzyk, Local and Online Algorithms for Facility Location, Universität
    Paderborn, 2013.
date_created: 2017-10-17T12:42:32Z
date_updated: 2022-01-06T07:01:38Z
ddc:
- '040'
department:
- _id: '63'
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:44:13Z
  date_updated: 2018-03-15T10:44:13Z
  file_id: '1302'
  file_name: 514-DissertationPietrzyk.pdf
  file_size: 790821
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:44:13Z
has_accepted_license: '1'
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
supervisor:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
title: Local and Online Algorithms for Facility Location
type: dissertation
user_id: '477'
year: '2013'
...
---
_id: '522'
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
citation:
  ama: 'Feldotto M. <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous
    Bandwidths</i>. Universität Paderborn; 2013.'
  apa: 'Feldotto, M. (2013). <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes
    with Heterogeneous Bandwidths</i>. Universität Paderborn.'
  bibtex: '@book{Feldotto_2013, title={HSkip+: A Self-Stabilizing Overlay Network
    for Nodes with Heterogeneous Bandwidths}, publisher={Universität Paderborn}, author={Feldotto,
    Matthias}, year={2013} }'
  chicago: 'Feldotto, Matthias. <i>HSkip+: A Self-Stabilizing Overlay Network for
    Nodes with Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.'
  ieee: 'M. Feldotto, <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes with
    Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.'
  mla: 'Feldotto, Matthias. <i>HSkip+: A Self-Stabilizing Overlay Network for Nodes
    with Heterogeneous Bandwidths</i>. Universität Paderborn, 2013.'
  short: 'M. Feldotto, HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous
    Bandwidths, Universität Paderborn, 2013.'
date_created: 2017-10-17T12:42:34Z
date_updated: 2022-01-06T07:01:47Z
department:
- _id: '79'
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Teilprojekt A
- _id: '5'
  name: SFB 901 - Subprojekt A1
publisher: Universität Paderborn
status: public
supervisor:
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
title: 'HSkip+: A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths'
type: mastersthesis
user_id: '14052'
year: '2013'
...
---
_id: '524'
abstract:
- lang: eng
  text: 'We study the complexity theory for the local distributed setting introduced
    by Korman, Peleg and Fraigniaud. They have defined three complexity classes LD
    (Local Decision), NLD (Nondeterministic Local Decision) and NLD^#n. The class
    LD consists of all languages which can be decided with a constant number of communication
    rounds. The class NLD consists of all languages which can be verified by a nondeterministic
    algorithm with a constant number of communication rounds. In order to define the
    nondeterministic classes, they have transferred the notation of nondeterminism
    into the distributed setting by the use of certificates and verifiers. The class
    NLD^#n consists of all languages which can be verified by a nondeterministic algorithm
    where each node has access to an oracle for the number of nodes. They have shown
    the hierarchy LD subset NLD subset NLD^#n. Our main contributions are strict hierarchies
    within the classes defined by Korman, Peleg and Fraigniaud. We define additional
    complexity classes: the class LD(t) consists of all languages which can be decided
    with at most t communication rounds. The class NLD-O(f) consists of all languages
    which can be verified by a local verifier such that the size of the certificates
    that are needed to verify the language are bounded by a function from O(f). Our
    main results are refined strict hierarchies within these nondeterministic classes.'
author:
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Kamil
  full_name: Swirkot, Kamil
  last_name: Swirkot
citation:
  ama: Meyer auf der Heide F, Swirkot K. Hierarchies in Local Distributed Decision.
    2013.
  apa: Meyer auf der Heide, F., &#38; Swirkot, K. (2013). Hierarchies in Local Distributed
    Decision. arXiv.
  bibtex: '@article{Meyer auf der Heide_Swirkot_2013, title={Hierarchies in Local
    Distributed Decision}, publisher={arXiv}, author={Meyer auf der Heide, Friedhelm
    and Swirkot, Kamil}, year={2013} }'
  chicago: Meyer auf der Heide, Friedhelm, and Kamil Swirkot. “Hierarchies in Local
    Distributed Decision.” arXiv, 2013.
  ieee: F. Meyer auf der Heide and K. Swirkot, “Hierarchies in Local Distributed Decision.”
    arXiv, 2013.
  mla: Meyer auf der Heide, Friedhelm, and Kamil Swirkot. <i>Hierarchies in Local
    Distributed Decision</i>. arXiv, 2013.
  short: F. Meyer auf der Heide, K. Swirkot, (2013).
date_created: 2017-10-17T12:42:34Z
date_updated: 2022-01-06T07:01:48Z
ddc:
- '040'
department:
- _id: '63'
external_id:
  arxiv:
  - '1311.7229'
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:37:07Z
  date_updated: 2018-03-15T10:37:07Z
  file_id: '1296'
  file_name: 524-paper_01.pdf
  file_size: 534906
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:37:07Z
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
publisher: arXiv
status: public
title: Hierarchies in Local Distributed Decision
type: preprint
user_id: '15415'
year: '2013'
...
---
_id: '526'
author:
- first_name: Alexander
  full_name: Mäcker, Alexander
  id: '13536'
  last_name: Mäcker
citation:
  ama: Mäcker A. <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität
    Paderborn; 2013.
  apa: Mäcker, A. (2013). <i>Greedy Network Creation With Heavy And Light Edges</i>.
    Universität Paderborn.
  bibtex: '@book{Mäcker_2013, title={Greedy Network Creation With Heavy And Light
    Edges}, publisher={Universität Paderborn}, author={Mäcker, Alexander}, year={2013}
    }'
  chicago: Mäcker, Alexander. <i>Greedy Network Creation With Heavy And Light Edges</i>.
    Universität Paderborn, 2013.
  ieee: A. Mäcker, <i>Greedy Network Creation With Heavy And Light Edges</i>. Universität
    Paderborn, 2013.
  mla: Mäcker, Alexander. <i>Greedy Network Creation With Heavy And Light Edges</i>.
    Universität Paderborn, 2013.
  short: A. Mäcker, Greedy Network Creation With Heavy And Light Edges, Universität
    Paderborn, 2013.
date_created: 2017-10-17T12:42:35Z
date_updated: 2022-01-06T07:01:48Z
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: Greedy Network Creation With Heavy And Light Edges
type: mastersthesis
user_id: '15504'
year: '2013'
...
---
_id: '537'
author:
- first_name: Stefan
  full_name: Heindorf, Stefan
  last_name: Heindorf
citation:
  ama: Heindorf S. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn;
    2013.
  apa: Heindorf, S. (2013). <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn.
  bibtex: '@book{Heindorf_2013, title={Dispersion of Multi-Robot Teams}, publisher={Universität
    Paderborn}, author={Heindorf, Stefan}, year={2013} }'
  chicago: Heindorf, Stefan. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn,
    2013.
  ieee: S. Heindorf, <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn,
    2013.
  mla: Heindorf, Stefan. <i>Dispersion of Multi-Robot Teams</i>. Universität Paderborn,
    2013.
  short: S. Heindorf, Dispersion of Multi-Robot Teams, Universität Paderborn, 2013.
date_created: 2017-10-17T12:42:37Z
date_updated: 2022-01-06T07:01:50Z
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: Dispersion of Multi-Robot Teams
type: mastersthesis
user_id: '15504'
year: '2013'
...
---
_id: '541'
abstract:
- lang: eng
  text: Existing solutions for gossip-based aggregation in peer-to-peer networks use
    epochs to calculate a global estimation from an initial static set of local values.
    Once the estimation converges system-wide, a new epoch is started with fresh initial
    values. Long epochs result in precise estimations based on old measurements and
    short epochs result in imprecise aggregated estimations. In contrast to this approach,
    we present in this paper a continuous, epoch-less approach which considers fresh
    local values in every round of the gossip-based aggregation. By using an approach
    for dynamic information aging, inaccurate values and values from left peers fade
    from the aggregation memory. Evaluation shows that the presented approach for
    continuous information aggregation in peer-to-peer systems monitors the system
    performance precisely, adapts to changes and is lightweight to operate.
author:
- first_name: Kalman
  full_name: Graffi, Kalman
  last_name: Graffi
- first_name: Vitaly
  full_name: Rapp, Vitaly
  last_name: Rapp
citation:
  ama: 'Graffi K, Rapp V. Continuous Gossip-based Aggregation through Dynamic Information
    Aging. In: <i>Proceedings of the International Conference on Computer Communications
    and Networks (ICCCN’13)</i>. ; 2013:1-7. doi:<a href="https://doi.org/10.1109/ICCCN.2013.6614118">10.1109/ICCCN.2013.6614118</a>'
  apa: Graffi, K., &#38; Rapp, V. (2013). Continuous Gossip-based Aggregation through
    Dynamic Information Aging. In <i>Proceedings of the International Conference on
    Computer Communications and Networks (ICCCN’13)</i> (pp. 1–7). <a href="https://doi.org/10.1109/ICCCN.2013.6614118">https://doi.org/10.1109/ICCCN.2013.6614118</a>
  bibtex: '@inproceedings{Graffi_Rapp_2013, title={Continuous Gossip-based Aggregation
    through Dynamic Information Aging}, DOI={<a href="https://doi.org/10.1109/ICCCN.2013.6614118">10.1109/ICCCN.2013.6614118</a>},
    booktitle={Proceedings of the International Conference on Computer Communications
    and Networks (ICCCN’13)}, author={Graffi, Kalman and Rapp, Vitaly}, year={2013},
    pages={1–7} }'
  chicago: Graffi, Kalman, and Vitaly Rapp. “Continuous Gossip-Based Aggregation through
    Dynamic Information Aging.” In <i>Proceedings of the International Conference
    on Computer Communications and Networks (ICCCN’13)</i>, 1–7, 2013. <a href="https://doi.org/10.1109/ICCCN.2013.6614118">https://doi.org/10.1109/ICCCN.2013.6614118</a>.
  ieee: K. Graffi and V. Rapp, “Continuous Gossip-based Aggregation through Dynamic
    Information Aging,” in <i>Proceedings of the International Conference on Computer
    Communications and Networks (ICCCN’13)</i>, 2013, pp. 1–7.
  mla: Graffi, Kalman, and Vitaly Rapp. “Continuous Gossip-Based Aggregation through
    Dynamic Information Aging.” <i>Proceedings of the International Conference on
    Computer Communications and Networks (ICCCN’13)</i>, 2013, pp. 1–7, doi:<a href="https://doi.org/10.1109/ICCCN.2013.6614118">10.1109/ICCCN.2013.6614118</a>.
  short: 'K. Graffi, V. Rapp, in: Proceedings of the International Conference on Computer
    Communications and Networks (ICCCN’13), 2013, pp. 1–7.'
date_created: 2017-10-17T12:42:37Z
date_updated: 2022-01-06T07:01:52Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/ICCCN.2013.6614118
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:33:20Z
  date_updated: 2018-03-15T10:33:20Z
  file_id: '1290'
  file_name: 541-Continuous.Gossip.based.Aggregation.Through.Dynamic.Information.Aging.pdf
  file_size: 272960
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:33:20Z
has_accepted_license: '1'
language:
- iso: eng
page: 1-7
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 International Conference on Computer Communications
  and Networks (ICCCN'13)
status: public
title: Continuous Gossip-based Aggregation through Dynamic Information Aging
type: conference
user_id: '477'
year: '2013'
...
---
_id: '544'
abstract:
- lang: eng
  text: Comparative evaluations of peer-to-peer protocols through simulations are
    a viable approach to judge the performance and costs of the individual protocols
    in large-scale networks. In order to support this work, we enhanced the peer-to-peer
    systems simulator PeerfactSim.KOM with a fine-grained analyzer concept, with exhaustive
    automated measurements and gnuplot generators as well as a coordination control
    to evaluate a set of experiment setups in parallel. Thus, by configuring all experiments
    and protocols only once and starting the simulator, all desired measurements are
    performed, analyzed, evaluated and combined, resulting in a holistic environment
    for the comparative evaluation of peer-to-peer systems.
author:
- first_name: Matthias
  full_name: Feldotto, Matthias
  id: '14052'
  last_name: Feldotto
  orcid: 0000-0003-1348-6516
- first_name: Kalman
  full_name: Graffi, Kalman
  last_name: Graffi
citation:
  ama: 'Feldotto M, Graffi K. Comparative Evaluation of Peer-to-Peer Systems Using
    PeerfactSim.KOM. In: <i>Proceedings of the International Conference on High Performance
    Computing and Simulation (HPCS’13)</i>. ; 2013:99-106. doi:<a href="https://doi.org/10.1109/HPCSim.2013.6641399">10.1109/HPCSim.2013.6641399</a>'
  apa: Feldotto, M., &#38; Graffi, K. (2013). Comparative Evaluation of Peer-to-Peer
    Systems Using PeerfactSim.KOM. In <i>Proceedings of the International Conference
    on High Performance Computing and Simulation (HPCS’13)</i> (pp. 99–106). <a href="https://doi.org/10.1109/HPCSim.2013.6641399">https://doi.org/10.1109/HPCSim.2013.6641399</a>
  bibtex: '@inproceedings{Feldotto_Graffi_2013, title={Comparative Evaluation of Peer-to-Peer
    Systems Using PeerfactSim.KOM}, DOI={<a href="https://doi.org/10.1109/HPCSim.2013.6641399">10.1109/HPCSim.2013.6641399</a>},
    booktitle={Proceedings of the International Conference on High Performance Computing
    and Simulation (HPCS’13)}, author={Feldotto, Matthias and Graffi, Kalman}, year={2013},
    pages={99–106} }'
  chicago: Feldotto, Matthias, and Kalman Graffi. “Comparative Evaluation of Peer-to-Peer
    Systems Using PeerfactSim.KOM.” In <i>Proceedings of the International Conference
    on High Performance Computing and Simulation (HPCS’13)</i>, 99–106, 2013. <a href="https://doi.org/10.1109/HPCSim.2013.6641399">https://doi.org/10.1109/HPCSim.2013.6641399</a>.
  ieee: M. Feldotto and K. Graffi, “Comparative Evaluation of Peer-to-Peer Systems
    Using PeerfactSim.KOM,” in <i>Proceedings of the International Conference on High
    Performance Computing and Simulation (HPCS’13)</i>, 2013, pp. 99–106.
  mla: Feldotto, Matthias, and Kalman Graffi. “Comparative Evaluation of Peer-to-Peer
    Systems Using PeerfactSim.KOM.” <i>Proceedings of the International Conference
    on High Performance Computing and Simulation (HPCS’13)</i>, 2013, pp. 99–106,
    doi:<a href="https://doi.org/10.1109/HPCSim.2013.6641399">10.1109/HPCSim.2013.6641399</a>.
  short: 'M. Feldotto, K. Graffi, in: Proceedings of the International Conference
    on High Performance Computing and Simulation (HPCS’13), 2013, pp. 99–106.'
date_created: 2017-10-17T12:42:38Z
date_updated: 2022-01-06T07:01:53Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/HPCSim.2013.6641399
file:
- access_level: closed
  content_type: application/pdf
  creator: florida
  date_created: 2018-03-15T10:32:17Z
  date_updated: 2018-03-15T10:32:17Z
  file_id: '1288'
  file_name: 544-FeldGraffi13.pdf
  file_size: 899441
  relation: main_file
  success: 1
file_date_updated: 2018-03-15T10:32:17Z
has_accepted_license: '1'
language:
- iso: eng
page: 99-106
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 International Conference on High Performance Computing
  and Simulation (HPCS'13)
status: public
title: Comparative Evaluation of Peer-to-Peer Systems Using PeerfactSim.KOM
type: conference
user_id: '14052'
year: '2013'
...
---
_id: '545'
author:
- first_name: Fritz
  full_name: Blumentritt, Fritz
  last_name: Blumentritt
citation:
  ama: Blumentritt F. <i>Cliquenbildung in verteilten Systemen</i>. Universität Paderborn;
    2013.
  apa: Blumentritt, F. (2013). <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn.
  bibtex: '@book{Blumentritt_2013, title={Cliquenbildung in verteilten Systemen},
    publisher={Universität Paderborn}, author={Blumentritt, Fritz}, year={2013} }'
  chicago: Blumentritt, Fritz. <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn, 2013.
  ieee: F. Blumentritt, <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn, 2013.
  mla: Blumentritt, Fritz. <i>Cliquenbildung in verteilten Systemen</i>. Universität
    Paderborn, 2013.
  short: F. Blumentritt, Cliquenbildung in verteilten Systemen, Universität Paderborn,
    2013.
date_created: 2017-10-17T12:42:38Z
date_updated: 2022-01-06T07:01:54Z
language:
- iso: ger
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: Cliquenbildung in verteilten Systemen
type: bachelorsthesis
user_id: '477'
year: '2013'
...