---
_id: '546'
abstract:
- lang: eng
text: Self-stabilization is the property of a system to transfer itself regardless
of the initial state into a legitimate state. Chord as a simple, decentralized
and scalable distributed hash table is an ideal showcase to introduce self-stabilization
for p2p overlays. In this paper, we present Re-Chord, a self-stabilizing version
of Chord. We show, that the stabilization process is functional, but prone to
strong churn. For that, we present Ca-Re-Chord, a churn resistant version of Re-Chord,
that allows the creation of a useful DHT in any kind of graph regardless of the
initial state. Simulation results attest the churn resistance and good performance
of Ca-Re-Chord.
author:
- first_name: Kalman
full_name: Graffi, Kalman
last_name: Graffi
- first_name: Markus
full_name: Benter, Markus
last_name: Benter
- first_name: Mohammad
full_name: Divband, Mohammad
last_name: Divband
- first_name: Sebastian
full_name: Kniesburges, Sebastian
last_name: Kniesburges
- first_name: Andreas
full_name: Koutsopoulos, Andreas
last_name: Koutsopoulos
citation:
ama: 'Graffi K, Benter M, Divband M, Kniesburges S, Koutsopoulos A. Ca-Re-Chord:
A Churn Resistant Self-stabilizing Chord Overlay Network. In: Proceedings of
the Conference on Networked Systems (NetSys). ; 2013:27-34. doi:10.1109/NetSys.2013.11'
apa: 'Graffi, K., Benter, M., Divband, M., Kniesburges, S., & Koutsopoulos,
A. (2013). Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network.
In Proceedings of the Conference on Networked Systems (NetSys) (pp. 27–34).
https://doi.org/10.1109/NetSys.2013.11'
bibtex: '@inproceedings{Graffi_Benter_Divband_Kniesburges_Koutsopoulos_2013, title={Ca-Re-Chord:
A Churn Resistant Self-stabilizing Chord Overlay Network}, DOI={10.1109/NetSys.2013.11},
booktitle={Proceedings of the Conference on Networked Systems (NetSys)}, author={Graffi,
Kalman and Benter, Markus and Divband, Mohammad and Kniesburges, Sebastian and
Koutsopoulos, Andreas}, year={2013}, pages={27–34} }'
chicago: 'Graffi, Kalman, Markus Benter, Mohammad Divband, Sebastian Kniesburges,
and Andreas Koutsopoulos. “Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord
Overlay Network.” In Proceedings of the Conference on Networked Systems (NetSys),
27–34, 2013. https://doi.org/10.1109/NetSys.2013.11.'
ieee: 'K. Graffi, M. Benter, M. Divband, S. Kniesburges, and A. Koutsopoulos, “Ca-Re-Chord:
A Churn Resistant Self-stabilizing Chord Overlay Network,” in Proceedings of
the Conference on Networked Systems (NetSys), 2013, pp. 27–34.'
mla: 'Graffi, Kalman, et al. “Ca-Re-Chord: A Churn Resistant Self-Stabilizing Chord
Overlay Network.” Proceedings of the Conference on Networked Systems (NetSys),
2013, pp. 27–34, doi:10.1109/NetSys.2013.11.'
short: 'K. Graffi, M. Benter, M. Divband, S. Kniesburges, A. Koutsopoulos, in: Proceedings
of the Conference on Networked Systems (NetSys), 2013, pp. 27–34.'
date_created: 2017-10-17T12:42:38Z
date_updated: 2022-01-06T07:01:55Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/NetSys.2013.11
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:30:42Z
date_updated: 2018-03-15T10:30:42Z
file_id: '1286'
file_name: 546-Kalman.Graffi_CaReChord.A.Churn.Resistant.Selfstabilizing.Chord.Overlay.Network_02.pdf
file_size: 244841
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:30:42Z
has_accepted_license: '1'
page: 27-34
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '13'
name: SFB 901 - Subproject C1
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the Conference on Networked Systems (NetSys)
status: public
title: 'Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network'
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '548'
abstract:
- lang: eng
text: Peer-to-peer systems scale to millions of nodes and provide routing and storage
functions with best effort quality. In order to provide a guaranteed quality of
the overlay functions, even under strong dynamics in the network with regard to
peer capacities, online participation and usage patterns, we propose to calibrate
the peer-to-peer overlay and to autonomously learn which qualities can be reached.
For that, we simulate the peer-to-peer overlay systematically under a wide range
of parameter configurations and use neural networks to learn the effects of the
configurations on the quality metrics. Thus, by choosing a specific quality setting
by the overlay operator, the network can tune itself to the learned parameter
configurations that lead to the desired quality. Evaluation shows that the presented
self-calibration succeeds in learning the configuration-quality interdependencies
and that peer-to-peer systems can learn and adapt their behavior according to
desired quality goals.
author:
- first_name: Kalman
full_name: Graffi, Kalman
last_name: Graffi
- first_name: Timo
full_name: Klerx, Timo
last_name: Klerx
citation:
ama: 'Graffi K, Klerx T. Bootstrapping Skynet: Calibration and Autonomic Self-Control
of Structured Peer-to-Peer Networks. In: Proceedings of the International Conference
on Peer-to-Peer Computing (P2P’13). ; 2013:1-5. doi:10.1109/P2P.2013.6688720'
apa: 'Graffi, K., & Klerx, T. (2013). Bootstrapping Skynet: Calibration and
Autonomic Self-Control of Structured Peer-to-Peer Networks. In Proceedings
of the International Conference on Peer-to-Peer Computing (P2P’13) (pp. 1–5).
https://doi.org/10.1109/P2P.2013.6688720'
bibtex: '@inproceedings{Graffi_Klerx_2013, title={Bootstrapping Skynet: Calibration
and Autonomic Self-Control of Structured Peer-to-Peer Networks}, DOI={10.1109/P2P.2013.6688720},
booktitle={Proceedings of the International Conference on Peer-to-Peer Computing
(P2P’13)}, author={Graffi, Kalman and Klerx, Timo}, year={2013}, pages={1–5} }'
chicago: 'Graffi, Kalman, and Timo Klerx. “Bootstrapping Skynet: Calibration and
Autonomic Self-Control of Structured Peer-to-Peer Networks.” In Proceedings
of the International Conference on Peer-to-Peer Computing (P2P’13), 1–5, 2013.
https://doi.org/10.1109/P2P.2013.6688720.'
ieee: 'K. Graffi and T. Klerx, “Bootstrapping Skynet: Calibration and Autonomic
Self-Control of Structured Peer-to-Peer Networks,” in Proceedings of the International
Conference on Peer-to-Peer Computing (P2P’13), 2013, pp. 1–5.'
mla: 'Graffi, Kalman, and Timo Klerx. “Bootstrapping Skynet: Calibration and Autonomic
Self-Control of Structured Peer-to-Peer Networks.” Proceedings of the International
Conference on Peer-to-Peer Computing (P2P’13), 2013, pp. 1–5, doi:10.1109/P2P.2013.6688720.'
short: 'K. Graffi, T. Klerx, in: Proceedings of the International Conference on
Peer-to-Peer Computing (P2P’13), 2013, pp. 1–5.'
date_created: 2017-10-17T12:42:39Z
date_updated: 2022-01-06T07:01:56Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/P2P.2013.6688720
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:30:09Z
date_updated: 2018-03-15T10:30:09Z
file_id: '1285'
file_name: 548-Bootstrapping.Skynet.Calibration.and.Autonomic.Self-Control.of.Structured.P2P.Networks_01.pdf
file_size: 629234
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:30:09Z
has_accepted_license: '1'
language:
- iso: eng
page: 1-5
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 Peer-to-Peer Computing
(P2P'13)
status: public
title: 'Bootstrapping Skynet: Calibration and Autonomic Self-Control of Structured
Peer-to-Peer Networks'
type: conference
user_id: '477'
year: '2013'
...
---
_id: '555'
author:
- first_name: Alexander
full_name: Setzer, Alexander
id: '11108'
last_name: Setzer
citation:
ama: Setzer A. Approximation Algorithms for the Linear Arrangement of Special
Classes of Graphs. Universität Paderborn; 2013.
apa: Setzer, A. (2013). Approximation Algorithms for the Linear Arrangement of
Special Classes of Graphs. 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. Approximation Algorithms for the Linear Arrangement
of Special Classes of Graphs. Universität Paderborn, 2013.
ieee: A. Setzer, Approximation Algorithms for the Linear Arrangement of Special
Classes of Graphs. Universität Paderborn, 2013.
mla: Setzer, Alexander. Approximation Algorithms for the Linear Arrangement of
Special Classes of Graphs. 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: '558'
citation:
ama: Flocchini P, Gao J, Kranakis E, Meyer auf der Heide F, eds. Algorithms for
Sensor Systems - 9th International Symposium on Algorithms and Experiments for
Sensor Systems, Wireless Networks and Distributed Robotics. Vol 8243. Springer;
2013. doi:10.1007/978-3-642-45346-5
apa: 'Flocchini, P., Gao, J., Kranakis, E., & Meyer auf der Heide, F. (Eds.).
(2013). Algorithms for Sensor Systems - 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(Vol. 8243). Presented at the ALGOSENSORS 2013, Sophia Antipolis, France: Springer.
https://doi.org/10.1007/978-3-642-45346-5'
bibtex: '@book{Flocchini_Gao_Kranakis_Meyer auf der Heide_2013, series={LNCS}, title={Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics}, volume={8243},
DOI={10.1007/978-3-642-45346-5},
publisher={Springer}, year={2013}, collection={LNCS} }'
chicago: Flocchini, Paola, Jie Gao, Evangelos Kranakis, and Friedhelm Meyer auf
der Heide, eds. Algorithms for Sensor Systems - 9th International Symposium
on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed
Robotics. Vol. 8243. LNCS. Springer, 2013. https://doi.org/10.1007/978-3-642-45346-5.
ieee: P. Flocchini, J. Gao, E. Kranakis, and F. Meyer auf der Heide, Eds., Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics, vol. 8243.
Springer, 2013.
mla: Flocchini, Paola, et al., editors. Algorithms for Sensor Systems - 9th International
Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks
and Distributed Robotics. Vol. 8243, Springer, 2013, doi:10.1007/978-3-642-45346-5.
short: P. Flocchini, J. Gao, E. Kranakis, F. Meyer auf der Heide, eds., Algorithms
for Sensor Systems - 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics, Springer, 2013.
conference:
end_date: 2013-09-06
location: Sophia Antipolis, France
name: ALGOSENSORS 2013
start_date: 2013-09-05
date_created: 2017-10-17T12:42:41Z
date_updated: 2022-01-06T07:02:02Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-642-45346-5
editor:
- first_name: Paola
full_name: Flocchini, Paola
last_name: Flocchini
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
- first_name: Evangelos
full_name: Kranakis, Evangelos
last_name: Kranakis
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T16:29:07Z
date_updated: 2018-11-02T16:29:07Z
file_id: '5327'
file_name: 2014_Book_AlgorithmsForSensorSystems-1.pdf
file_size: 9186107
relation: main_file
success: 1
file_date_updated: 2018-11-02T16:29:07Z
has_accepted_license: '1'
intvolume: ' 8243'
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: Springer
series_title: LNCS
status: public
title: Algorithms for Sensor Systems - 9th International Symposium on Algorithms and
Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
type: conference_editor
user_id: '477'
volume: 8243
year: '2013'
...
---
_id: '559'
abstract:
- lang: eng
text: Distributed hash tables are very versatile to use, as distributed storage
is a desirable feature for various applications. Typical structured overlays like
Chord, Pastry or Kademlia consider only homogeneous nodes with equal capacities,
which does not resemble reality. In a practical use case, nodes might get overloaded
by storing popular data. In this paper, we present a general approach to enable
capacity awareness and load-balancing capability of homogeneous structured overlays.
We introduce a hierarchical second structured overlay aside, which allows efficient
capacity-based access on the nodes in the system as hosting mirrors. Simulation
results show that the structured overlay is able to store various contents, such
as of a social network, with only a negligible number of overloaded peers. Content,
even if very popular, is hosted by easily findable capable peers. Thus, long-existing
and well-evaluated overlays like Chord or Pastry can be used to create attractive
DHT-based applications.
author:
- first_name: Philip
full_name: Wette, Philip
last_name: Wette
- first_name: Kalman
full_name: Graffi, Kalman
last_name: Graffi
citation:
ama: 'Wette P, Graffi K. Adding Capacity-Aware Storage Indirection to Homogeneous
Distributed Hash Tables. In: Proceedings of the Conference on Networked Systems
(NetSys). ; 2013:35-42. doi:10.1109/NetSys.2013.9'
apa: Wette, P., & Graffi, K. (2013). Adding Capacity-Aware Storage Indirection
to Homogeneous Distributed Hash Tables. In Proceedings of the Conference on
Networked Systems (NetSys) (pp. 35–42). https://doi.org/10.1109/NetSys.2013.9
bibtex: '@inproceedings{Wette_Graffi_2013, title={Adding Capacity-Aware Storage
Indirection to Homogeneous Distributed Hash Tables}, DOI={10.1109/NetSys.2013.9},
booktitle={Proceedings of the Conference on Networked Systems (NetSys)}, author={Wette,
Philip and Graffi, Kalman}, year={2013}, pages={35–42} }'
chicago: Wette, Philip, and Kalman Graffi. “Adding Capacity-Aware Storage Indirection
to Homogeneous Distributed Hash Tables.” In Proceedings of the Conference on
Networked Systems (NetSys), 35–42, 2013. https://doi.org/10.1109/NetSys.2013.9.
ieee: P. Wette and K. Graffi, “Adding Capacity-Aware Storage Indirection to Homogeneous
Distributed Hash Tables,” in Proceedings of the Conference on Networked Systems
(NetSys), 2013, pp. 35–42.
mla: Wette, Philip, and Kalman Graffi. “Adding Capacity-Aware Storage Indirection
to Homogeneous Distributed Hash Tables.” Proceedings of the Conference on Networked
Systems (NetSys), 2013, pp. 35–42, doi:10.1109/NetSys.2013.9.
short: 'P. Wette, K. Graffi, in: Proceedings of the Conference on Networked Systems
(NetSys), 2013, pp. 35–42.'
date_created: 2017-10-17T12:42:41Z
date_updated: 2022-01-06T07:02:04Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/NetSys.2013.9
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:27:21Z
date_updated: 2018-03-15T10:27:21Z
file_id: '1282'
file_name: 559-Adding.Capacity.Aware.Storage.Indirection.to.Homogeneous.Distributed.Hash.Tables.pdf
file_size: 734618
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:27:21Z
has_accepted_license: '1'
language:
- iso: eng
page: 35-42
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 Conference on Networked Systems (NetSys)
status: public
title: Adding Capacity-Aware Storage Indirection to Homogeneous Distributed Hash Tables
type: conference
user_id: '477'
year: '2013'
...
---
_id: '562'
abstract:
- lang: eng
text: In Distributed Cloud Computing, applications are deployed across many data
centres at topologically diverse locations to improved network-related quality
of service (QoS). As we focus on interactive applications, we minimize the latency
between users and an application by allocating Cloud resources nearby the customers.
Allocating resources at all locations will result in the best latency but also
in the highest expenses. So we need to find an optimal subset of locations which
reduces the latency but also the expenses – the facility location problem (FLP).
In addition, we consider resource capacity restrictions, as a resource can only
serve a limited amount of users. An FLP can be globally solved. Additionally,
we propose a local, distributed heuristic. This heuristic is running within the
network and does not depend on a global component. No distributed, local approximations
for the capacitated FLP have been proposed so far due to the complexity of the
problem. We compared the heuristic with an optimal solution obtained from a mixed
integer program for different network topologies. We investigated the influence
of different parameters like overall resource utilization or different latency
weights.
author:
- first_name: Matthias
full_name: Keller, Matthias
last_name: Keller
- first_name: Stefan
full_name: Pawlik, Stefan
last_name: Pawlik
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
- first_name: Holger
full_name: Karl, Holger
id: '126'
last_name: Karl
citation:
ama: 'Keller M, Pawlik S, Pietrzyk P, Karl H. A Local Heuristic for Latency-Optimized
Distributed Cloud Deployment. In: Proceedings of the 6th International Conference
on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud Computing.
; 2013:429-434. doi:10.1109/UCC.2013.85'
apa: Keller, M., Pawlik, S., Pietrzyk, P., & Karl, H. (2013). A Local Heuristic
for Latency-Optimized Distributed Cloud Deployment. In Proceedings of the 6th
International Conference on Utility and Cloud Computing (UCC) workshop on Distributed
cloud computing (pp. 429–434). https://doi.org/10.1109/UCC.2013.85
bibtex: '@inproceedings{Keller_Pawlik_Pietrzyk_Karl_2013, title={A Local Heuristic
for Latency-Optimized Distributed Cloud Deployment}, DOI={10.1109/UCC.2013.85},
booktitle={Proceedings of the 6th International Conference on Utility and Cloud
Computing (UCC) workshop on Distributed cloud computing}, author={Keller, Matthias
and Pawlik, Stefan and Pietrzyk, Peter and Karl, Holger}, year={2013}, pages={429–434}
}'
chicago: Keller, Matthias, Stefan Pawlik, Peter Pietrzyk, and Holger Karl. “A Local
Heuristic for Latency-Optimized Distributed Cloud Deployment.” In Proceedings
of the 6th International Conference on Utility and Cloud Computing (UCC) Workshop
on Distributed Cloud Computing, 429–34, 2013. https://doi.org/10.1109/UCC.2013.85.
ieee: M. Keller, S. Pawlik, P. Pietrzyk, and H. Karl, “A Local Heuristic for Latency-Optimized
Distributed Cloud Deployment,” in Proceedings of the 6th International Conference
on Utility and Cloud Computing (UCC) workshop on Distributed cloud computing,
2013, pp. 429–434.
mla: Keller, Matthias, et al. “A Local Heuristic for Latency-Optimized Distributed
Cloud Deployment.” Proceedings of the 6th International Conference on Utility
and Cloud Computing (UCC) Workshop on Distributed Cloud Computing, 2013, pp.
429–34, doi:10.1109/UCC.2013.85.
short: 'M. Keller, S. Pawlik, P. Pietrzyk, H. Karl, in: Proceedings of the 6th International
Conference on Utility and Cloud Computing (UCC) Workshop on Distributed Cloud
Computing, 2013, pp. 429–434.'
date_created: 2017-10-17T12:42:41Z
date_updated: 2022-01-06T07:02:11Z
ddc:
- '040'
department:
- _id: '75'
- _id: '63'
doi: 10.1109/UCC.2013.85
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:25:45Z
date_updated: 2018-03-15T10:25:45Z
file_id: '1279'
file_name: 562-dcc13_paper.pdf
file_size: 347873
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:25:45Z
has_accepted_license: '1'
language:
- iso: eng
page: 429-434
project:
- _id: '1'
name: SFB 901
- _id: '6'
name: SFB 901 - Subprojekt A2
- _id: '5'
name: SFB 901 - Subproject A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 6th International Conference on Utility and Cloud
Computing (UCC) workshop on Distributed cloud computing
status: public
title: A Local Heuristic for Latency-Optimized Distributed Cloud Deployment
type: conference
user_id: '477'
year: '2013'
...
---
_id: '563'
abstract:
- lang: eng
text: Dominating set based virtual backbones are used for rou-ting in wireless ad-hoc
networks. Such backbones receive and transmit messages from/to every node in the
network. Existing distributed algorithms only consider undirected graphs, which
model symmetric networks with uniform transmission ranges. We are particularly
interested in the well-established disk graphs, which model asymmetric networks
with non-uniform transmission ranges. The corresponding graph theoretic problem
seeks a strongly connected dominating-absorbent set of minimum cardinality in
a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent
set if the subgraph induced by these nodes is strongly connected and each node
in the graph is either in the set or has both an in-neighbor and an out-neighbor
in it. We introduce the first distributed algorithm for this problem in disk graphs.
The algorithm gives an O(k^4) -approximation ratio and has a runtime bound of
O(Diam) where Diam is the diameter of the graph and k denotes the transmission
ratio r_{max}/r_{min} with r_{max} and r_{min} being the maximum and minimum transmission
range, respectively. Moreover, we apply our algorithm on the subgraph of disk
graphs consisting of only bidirectional edges. Our algorithm gives an O(ln k)
-approximation and a runtime bound of O(k^8 log^∗ n) , which, for bounded k ,
is an optimal approximation for the problem, following Lenzen and Wattenhofer’s
Ω(log^∗ n) runtime lower bound for distributed constant approximation in disk
graphs.
author:
- first_name: Christine
full_name: Markarian, Christine
id: '37612'
last_name: Markarian
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Michael
full_name: Schubert, Michael
last_name: Schubert
citation:
ama: 'Markarian C, Meyer auf der Heide F, Schubert M. A Distributed Approximation
Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless
Ad-Hoc Networks. In: Proceedings of the 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(ALGOSENSORS). LNCS. ; 2013:217-227. doi:10.1007/978-3-642-45346-5_16'
apa: Markarian, C., Meyer auf der Heide, F., & Schubert, M. (2013). A Distributed
Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric
Wireless Ad-Hoc Networks. In Proceedings of the 9th International Symposium
on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed
Robotics (ALGOSENSORS) (pp. 217–227). https://doi.org/10.1007/978-3-642-45346-5_16
bibtex: '@inproceedings{Markarian_Meyer auf der Heide_Schubert_2013, series={LNCS},
title={A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks}, DOI={10.1007/978-3-642-45346-5_16},
booktitle={Proceedings of the 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)},
author={Markarian, Christine and Meyer auf der Heide, Friedhelm and Schubert,
Michael}, year={2013}, pages={217–227}, collection={LNCS} }'
chicago: Markarian, Christine, Friedhelm Meyer auf der Heide, and Michael Schubert.
“A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks.” In Proceedings of the 9th International
Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks
and Distributed Robotics (ALGOSENSORS), 217–27. LNCS, 2013. https://doi.org/10.1007/978-3-642-45346-5_16.
ieee: C. Markarian, F. Meyer auf der Heide, and M. Schubert, “A Distributed Approximation
Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless
Ad-Hoc Networks,” in Proceedings of the 9th International Symposium on Algorithms
and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics
(ALGOSENSORS), 2013, pp. 217–227.
mla: Markarian, Christine, et al. “A Distributed Approximation Algorithm for Strongly
Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks.” Proceedings
of the 9th International Symposium on Algorithms and Experiments for Sensor Systems,
Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–27,
doi:10.1007/978-3-642-45346-5_16.
short: 'C. Markarian, F. Meyer auf der Heide, M. Schubert, in: Proceedings of the
9th International Symposium on Algorithms and Experiments for Sensor Systems,
Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 217–227.'
date_created: 2017-10-17T12:42:42Z
date_updated: 2022-01-06T07:02:13Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-45346-5_16
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:25:15Z
date_updated: 2018-03-15T10:25:15Z
file_id: '1278'
file_name: 563-978-3-642-45346-5_16.pdf
file_size: 348191
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:25:15Z
has_accepted_license: '1'
page: 217-227
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 9th International Symposium on Algorithms and Experiments
for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)
series_title: LNCS
status: public
title: A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent
Sets in Asymmetric Wireless Ad-Hoc Networks
type: conference
user_id: '477'
year: '2013'
...
---
_id: '564'
abstract:
- lang: eng
text: We consider the problem of resource discovery in distributed systems. In particular
we give an algorithm, such that each node in a network discovers the add ress
of any other node in the network. We model the knowledge of the nodes as a virtual
overlay network given by a directed graph such that complete knowledge of all
nodes corresponds to a complete graph in the overlay network. Although there are
several solutions for resource discovery, our solution is the first that achieves
worst-case optimal work for each node, i.e. the number of addresses (O(n)) or
bits (O(nlogn)) a node receives or sendscoincides with the lower bound, while
ensuring only a linearruntime (O(n)) on the number of rounds.
author:
- first_name: Sebastian
full_name: Kniesburges, Sebastian
last_name: Kniesburges
- first_name: Andreas
full_name: Koutsopoulos, Andreas
last_name: Koutsopoulos
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Kniesburges S, Koutsopoulos A, Scheideler C. A Deterministic Worst-Case Message
Complexity Optimal Solution for Resource Discovery. In: Proceedings of 20th
International Colloqium on Structural Information and Communication Complexity
(SIROCCO). Lecture Notes in Computer Science. ; 2013:165-176. doi:10.1007/978-3-319-03578-9_14'
apa: Kniesburges, S., Koutsopoulos, A., & Scheideler, C. (2013). A Deterministic
Worst-Case Message Complexity Optimal Solution for Resource Discovery. In Proceedings
of 20th International Colloqium on Structural Information and Communication Complexity
(SIROCCO) (pp. 165–176). https://doi.org/10.1007/978-3-319-03578-9_14
bibtex: '@inproceedings{Kniesburges_Koutsopoulos_Scheideler_2013, series={Lecture
Notes in Computer Science}, title={A Deterministic Worst-Case Message Complexity
Optimal Solution for Resource Discovery}, DOI={10.1007/978-3-319-03578-9_14},
booktitle={Proceedings of 20th International Colloqium on Structural Information
and Communication Complexity (SIROCCO)}, author={Kniesburges, Sebastian and Koutsopoulos,
Andreas and Scheideler, Christian}, year={2013}, pages={165–176}, collection={Lecture
Notes in Computer Science} }'
chicago: Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler.
“A Deterministic Worst-Case Message Complexity Optimal Solution for Resource Discovery.”
In Proceedings of 20th International Colloqium on Structural Information and
Communication Complexity (SIROCCO), 165–76. Lecture Notes in Computer Science,
2013. https://doi.org/10.1007/978-3-319-03578-9_14.
ieee: S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A Deterministic Worst-Case
Message Complexity Optimal Solution for Resource Discovery,” in Proceedings
of 20th International Colloqium on Structural Information and Communication Complexity
(SIROCCO), 2013, pp. 165–176.
mla: Kniesburges, Sebastian, et al. “A Deterministic Worst-Case Message Complexity
Optimal Solution for Resource Discovery.” Proceedings of 20th International
Colloqium on Structural Information and Communication Complexity (SIROCCO),
2013, pp. 165–76, doi:10.1007/978-3-319-03578-9_14.
short: 'S. Kniesburges, A. Koutsopoulos, C. Scheideler, in: Proceedings of 20th
International Colloqium on Structural Information and Communication Complexity
(SIROCCO), 2013, pp. 165–176.'
date_created: 2017-10-17T12:42:42Z
date_updated: 2022-01-06T07:02:17Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-319-03578-9_14
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:24:40Z
date_updated: 2018-03-15T10:24:40Z
file_id: '1277'
file_name: 564-SIROCCO13.pdf
file_size: 168884
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:24:40Z
has_accepted_license: '1'
page: 165-176
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of 20th International Colloqium on Structural Information
and Communication Complexity (SIROCCO)
series_title: Lecture Notes in Computer Science
status: public
title: A Deterministic Worst-Case Message Complexity Optimal Solution for Resource
Discovery
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '570'
abstract:
- lang: eng
text: 'This article studies the construction of self-stabilizing topologies for
distributed systems. While recent research has focused on chain topologies where
nodes need to be linearized with respect to their identiers, we explore a natural
and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing
algorithm DStab which is based on the concept of \local Delaunay graphs" and which
forwards temporary edges in greedy fashion reminiscent of compass routing. DStab
constructs a Delaunay graph from any initial connected topology and in a distributed
manner in time O(n3) in the worst-case; if the initial network contains the Delaunay
graph, the convergence time is only O(n) rounds. DStab also ensures that individual
node joins and leaves aect a small part of the network only. Such self-stabilizing
Delaunay networks have interesting applications and our construction gives insights
into the necessary geometric reasoning that is required for higherdimensional
linearization problems.Keywords: Distributed Algorithms, Topology Control, Social
Networks'
author:
- first_name: Riko
full_name: Jacob, Riko
last_name: Jacob
- first_name: Stephan
full_name: Ritscher, Stephan
last_name: Ritscher
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological
self-stabilization: A distributed algorithm for Delaunay graphs. Theoretical
Computer Science. 2012:137-148. doi:10.1016/j.tcs.2012.07.029'
apa: 'Jacob, R., Ritscher, S., Scheideler, C., & Schmid, S. (2012). Towards
higher-dimensional topological self-stabilization: A distributed algorithm for
Delaunay graphs. Theoretical Computer Science, 137–148. https://doi.org/10.1016/j.tcs.2012.07.029'
bibtex: '@article{Jacob_Ritscher_Scheideler_Schmid_2012, title={Towards higher-dimensional
topological self-stabilization: A distributed algorithm for Delaunay graphs},
DOI={10.1016/j.tcs.2012.07.029},
journal={Theoretical Computer Science}, publisher={Elsevier}, author={Jacob, Riko
and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}, year={2012},
pages={137–148} }'
chicago: 'Jacob, Riko, Stephan Ritscher, Christian Scheideler, and Stefan Schmid.
“Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm
for Delaunay Graphs.” Theoretical Computer Science, 2012, 137–48. https://doi.org/10.1016/j.tcs.2012.07.029.'
ieee: 'R. Jacob, S. Ritscher, C. Scheideler, and S. Schmid, “Towards higher-dimensional
topological self-stabilization: A distributed algorithm for Delaunay graphs,”
Theoretical Computer Science, pp. 137–148, 2012.'
mla: 'Jacob, Riko, et al. “Towards Higher-Dimensional Topological Self-Stabilization:
A Distributed Algorithm for Delaunay Graphs.” Theoretical Computer Science,
Elsevier, 2012, pp. 137–48, doi:10.1016/j.tcs.2012.07.029.'
short: R. Jacob, S. Ritscher, C. Scheideler, S. Schmid, Theoretical Computer Science
(2012) 137–148.
date_created: 2017-10-17T12:42:43Z
date_updated: 2022-01-06T07:02:36Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1016/j.tcs.2012.07.029
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:16:20Z
date_updated: 2018-03-15T10:16:20Z
file_id: '1272'
file_name: 570-Delaunay-Journal.pdf
file_size: 250051
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:16:20Z
has_accepted_license: '1'
page: 137-148
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Theoretical Computer Science
publisher: Elsevier
status: public
title: 'Towards higher-dimensional topological self-stabilization: A distributed algorithm
for Delaunay graphs'
type: journal_article
user_id: '477'
year: '2012'
...
---
_id: '574'
abstract:
- lang: eng
text: 'We present Tiara — a self-stabilizing peer-to-peer network maintenance algorithm.
Tiara is truly deterministic which allows it to achieve exact performance bounds.
Tiara allows logarithmic searches and topology updates. It is based on a novel
sparse 0-1 skip list. We then describe its extension to a ringed structure and
to a skip-graph.Key words: Peer-to-peer networks, overlay networks, self-stabilization.'
author:
- first_name: Thomas
full_name: Clouser, Thomas
last_name: Clouser
- first_name: Mikhail
full_name: Nesterenko, Mikhail
last_name: Nesterenko
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Clouser T, Nesterenko M, Scheideler C. Tiara: A self-stabilizing deterministic
skip list and skip graph. Theoretical Computer Science. 2012:18-35. doi:10.1016/j.tcs.2011.12.079'
apa: 'Clouser, T., Nesterenko, M., & Scheideler, C. (2012). Tiara: A self-stabilizing
deterministic skip list and skip graph. Theoretical Computer Science, 18–35.
https://doi.org/10.1016/j.tcs.2011.12.079'
bibtex: '@article{Clouser_Nesterenko_Scheideler_2012, title={Tiara: A self-stabilizing
deterministic skip list and skip graph}, DOI={10.1016/j.tcs.2011.12.079},
journal={Theoretical Computer Science}, publisher={Elsevier}, author={Clouser,
Thomas and Nesterenko, Mikhail and Scheideler, Christian}, year={2012}, pages={18–35}
}'
chicago: 'Clouser, Thomas, Mikhail Nesterenko, and Christian Scheideler. “Tiara:
A Self-Stabilizing Deterministic Skip List and Skip Graph.” Theoretical Computer
Science, 2012, 18–35. https://doi.org/10.1016/j.tcs.2011.12.079.'
ieee: 'T. Clouser, M. Nesterenko, and C. Scheideler, “Tiara: A self-stabilizing
deterministic skip list and skip graph,” Theoretical Computer Science,
pp. 18–35, 2012.'
mla: 'Clouser, Thomas, et al. “Tiara: A Self-Stabilizing Deterministic Skip List
and Skip Graph.” Theoretical Computer Science, Elsevier, 2012, pp. 18–35,
doi:10.1016/j.tcs.2011.12.079.'
short: T. Clouser, M. Nesterenko, C. Scheideler, Theoretical Computer Science (2012)
18–35.
date_created: 2017-10-17T12:42:44Z
date_updated: 2022-01-06T07:02:38Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1016/j.tcs.2011.12.079
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:09:29Z
date_updated: 2018-03-15T09:09:29Z
file_id: '1268'
file_name: 574-tiara.pdf
file_size: 315843
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:09:29Z
has_accepted_license: '1'
page: 18-35
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Theoretical Computer Science
publisher: Elsevier
status: public
title: 'Tiara: A self-stabilizing deterministic skip list and skip graph'
type: journal_article
user_id: '477'
year: '2012'
...
---
_id: '575'
author:
- first_name: Lars
full_name: Bremer, Lars
last_name: Bremer
citation:
ama: Bremer L. Symbiotic Coupling of Peer-to-Peer and Cloud Systems. Universität
Paderborn; 2012.
apa: Bremer, L. (2012). Symbiotic Coupling of Peer-to-Peer and Cloud Systems.
Universität Paderborn.
bibtex: '@book{Bremer_2012, title={Symbiotic Coupling of Peer-to-Peer and Cloud
Systems}, publisher={Universität Paderborn}, author={Bremer, Lars}, year={2012}
}'
chicago: Bremer, Lars. Symbiotic Coupling of Peer-to-Peer and Cloud Systems.
Universität Paderborn, 2012.
ieee: L. Bremer, Symbiotic Coupling of Peer-to-Peer and Cloud Systems. Universität
Paderborn, 2012.
mla: Bremer, Lars. Symbiotic Coupling of Peer-to-Peer and Cloud Systems.
Universität Paderborn, 2012.
short: L. Bremer, Symbiotic Coupling of Peer-to-Peer and Cloud Systems, Universität
Paderborn, 2012.
date_created: 2017-10-17T12:42:44Z
date_updated: 2022-01-06T07:02:38Z
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: Symbiotic Coupling of Peer-to-Peer and Cloud Systems
type: mastersthesis
user_id: '15504'
year: '2012'
...
---
_id: '579'
abstract:
- lang: eng
text: A left-to-right maximum in a sequence of n numbers s_1, …, s_n is a number
that is strictly larger than all preceding numbers. In this article we present
a smoothed analysis of the number of left-to-right maxima in the presence of additive
random noise. We show that for every sequence of n numbers s_i ∈ [0,1] that are
perturbed by uniform noise from the interval [-ε,ε], the expected number of left-to-right
maxima is Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation
σ we obtain a bound of O((log3/2 n)/σ + log n).We apply our results to the analysis
of the smoothed height of binary search trees and the smoothed number of comparisons
in the quicksort algorithm and prove bounds of Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;n/ε
+ n log n), respectively, for uniform random noise from the interval [-ε,ε]. Our
results can also be applied to bound the smoothed number of points on a convex
hull of points in the two-dimensional plane and to smoothed motion complexity,
a concept we describe in this article. We bound how often one needs to update
a data structure storing the smallest axis-aligned box enclosing a set of points
moving in d-dimensional space.
author:
- first_name: Valentina
full_name: Damerow, Valentina
last_name: Damerow
- first_name: Bodo
full_name: Manthey, Bodo
last_name: Manthey
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Till
full_name: Tantau, Till
last_name: Tantau
citation:
ama: Damerow V, Manthey B, Meyer auf der Heide F, et al. Smoothed analysis of left-to-right
maxima with applications. Transactions on Algorithms. 2012;(3):30. doi:10.1145/2229163.2229174
apa: Damerow, V., Manthey, B., Meyer auf der Heide, F., Räcke, H., Scheideler, C.,
Sohler, C., & Tantau, T. (2012). Smoothed analysis of left-to-right maxima
with applications. Transactions on Algorithms, (3), 30. https://doi.org/10.1145/2229163.2229174
bibtex: '@article{Damerow_Manthey_Meyer auf der Heide_Räcke_Scheideler_Sohler_Tantau_2012,
title={Smoothed analysis of left-to-right maxima with applications}, DOI={10.1145/2229163.2229174},
number={3}, journal={Transactions on Algorithms}, publisher={ACM}, author={Damerow,
Valentina and Manthey, Bodo and Meyer auf der Heide, Friedhelm and Räcke, Harald
and Scheideler, Christian and Sohler, Christian and Tantau, Till}, year={2012},
pages={30} }'
chicago: 'Damerow, Valentina, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald
Räcke, Christian Scheideler, Christian Sohler, and Till Tantau. “Smoothed Analysis
of Left-to-Right Maxima with Applications.” Transactions on Algorithms,
no. 3 (2012): 30. https://doi.org/10.1145/2229163.2229174.'
ieee: V. Damerow et al., “Smoothed analysis of left-to-right maxima with
applications,” Transactions on Algorithms, no. 3, p. 30, 2012.
mla: Damerow, Valentina, et al. “Smoothed Analysis of Left-to-Right Maxima with
Applications.” Transactions on Algorithms, no. 3, ACM, 2012, p. 30, doi:10.1145/2229163.2229174.
short: V. Damerow, B. Manthey, F. Meyer auf der Heide, H. Räcke, C. Scheideler,
C. Sohler, T. Tantau, Transactions on Algorithms (2012) 30.
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:41Z
ddc:
- '040'
department:
- _id: '79'
- _id: '63'
doi: 10.1145/2229163.2229174
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:04:58Z
date_updated: 2018-03-15T09:04:58Z
file_id: '1266'
file_name: 579-a30-damerow.pdf
file_size: 329282
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:04:58Z
has_accepted_license: '1'
issue: '3'
page: '30'
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Transactions on Algorithms
publisher: ACM
status: public
title: Smoothed analysis of left-to-right maxima with applications
type: journal_article
user_id: '477'
year: '2012'
...
---
_id: '582'
author:
- first_name: Thim Frederik
full_name: Strothmann, Thim Frederik
id: '11319'
last_name: Strothmann
citation:
ama: Strothmann TF. Self-Optimizing Binary Search Trees - A Game Theoretic Approach.
Universität Paderborn; 2012.
apa: Strothmann, T. F. (2012). Self-Optimizing Binary Search Trees - A Game Theoretic
Approach. Universität Paderborn.
bibtex: '@book{Strothmann_2012, title={Self-Optimizing Binary Search Trees - A Game
Theoretic Approach}, publisher={Universität Paderborn}, author={Strothmann, Thim
Frederik}, year={2012} }'
chicago: Strothmann, Thim Frederik. Self-Optimizing Binary Search Trees - A Game
Theoretic Approach. Universität Paderborn, 2012.
ieee: T. F. Strothmann, Self-Optimizing Binary Search Trees - A Game Theoretic
Approach. Universität Paderborn, 2012.
mla: Strothmann, Thim Frederik. Self-Optimizing Binary Search Trees - A Game
Theoretic Approach. Universität Paderborn, 2012.
short: T.F. Strothmann, Self-Optimizing Binary Search Trees - A Game Theoretic Approach,
Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
department:
- _id: '79'
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: Universität Paderborn
status: public
title: Self-Optimizing Binary Search Trees - A Game Theoretic Approach
type: mastersthesis
user_id: '477'
year: '2012'
...
---
_id: '594'
author:
- first_name: Timo
full_name: Klerx, Timo
last_name: Klerx
citation:
ama: Klerx T. Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen
Netzen. Universität Paderborn; 2012.
apa: Klerx, T. (2012). Online Parameteroptimierung in P2P-Netzwerken mit Hilfe
von Neuronalen Netzen. Universität Paderborn.
bibtex: '@book{Klerx_2012, title={Online Parameteroptimierung in P2P-Netzwerken
mit Hilfe von Neuronalen Netzen}, publisher={Universität Paderborn}, author={Klerx,
Timo}, year={2012} }'
chicago: Klerx, Timo. Online Parameteroptimierung in P2P-Netzwerken mit Hilfe
von Neuronalen Netzen. Universität Paderborn, 2012.
ieee: T. Klerx, Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen
Netzen. Universität Paderborn, 2012.
mla: Klerx, Timo. Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von
Neuronalen Netzen. Universität Paderborn, 2012.
short: T. Klerx, Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen
Netzen, Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:47Z
date_updated: 2022-01-06T07:02:48Z
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: Online Parameteroptimierung in P2P-Netzwerken mit Hilfe von Neuronalen Netzen
type: mastersthesis
user_id: '477'
year: '2012'
...
---
_id: '600'
author:
- first_name: Björn
full_name: Feldkord, Björn
id: '22704'
last_name: Feldkord
citation:
ama: Feldkord B. Lokale Swaps und überholte Informationen in Basic Network Creation
Games. Universität Paderborn; 2012.
apa: Feldkord, B. (2012). Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn.
bibtex: '@book{Feldkord_2012, title={Lokale Swaps und überholte Informationen in
Basic Network Creation Games}, publisher={Universität Paderborn}, author={Feldkord,
Björn}, year={2012} }'
chicago: Feldkord, Björn. Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
ieee: B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
mla: Feldkord, Björn. Lokale Swaps und überholte Informationen in Basic Network
Creation Games. Universität Paderborn, 2012.
short: B. Feldkord, Lokale Swaps und überholte Informationen in Basic Network Creation
Games, Universität Paderborn, 2012.
date_created: 2017-10-17T12:42:49Z
date_updated: 2022-01-06T07:02:49Z
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: Lokale Swaps und überholte Informationen in Basic Network Creation Games
type: bachelorsthesis
user_id: '477'
year: '2012'
...
---
_id: '601'
abstract:
- lang: eng
text: Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen
Gel{\"a}nde. Es gibt keine zentrale Steuerung und die Roboter m{\"u}ssen sich
selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur
seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren
Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen.
In dieser Arbeit wird untersucht, unter welchen Voraussetzungen die Roboter sich
auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden
k{\"o}nnen. Daf{\"u}r werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen
vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden
obere und untere Schranken f{\"u}r die ben{\"o}tigte Anzahl Runden und die Bewegungsdistanz
gezeigt. In einigen F{\"a}llen wird außerdem die ben{\"o}tigte Bewegungsdistanz
mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie
auf der gleichen Instanz ben{\"o}tigen w{\"u}rde. So werden kompetititve Faktoren
hergeleitet.
author:
- first_name: Barbara
full_name: Kempkes, Barbara
last_name: Kempkes
citation:
ama: Kempkes B. Local Strategies for Robot Formation Problems. Vol 302. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn; 2012.
apa: Kempkes, B. (2012). Local strategies for robot formation problems (Vol.
302). Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn.
bibtex: '@book{Kempkes_2012, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn}, title={Local strategies for robot formation problems}, volume={302},
publisher={Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}, author={Kempkes,
Barbara}, year={2012}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts,
Paderborn} }'
chicago: Kempkes, Barbara. Local Strategies for Robot Formation Problems.
Vol. 302. Verlagsschriftenreihe Des Heinz Nixdorf Instituts, Paderborn. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
ieee: B. Kempkes, Local strategies for robot formation problems, vol. 302.
Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, 2012.
mla: Kempkes, Barbara. Local Strategies for Robot Formation Problems. Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
short: B. Kempkes, Local Strategies for Robot Formation Problems, Verlagsschriftenreihe
des Heinz Nixdorf Instituts, Paderborn, 2012.
date_created: 2017-10-17T12:42:49Z
date_updated: 2022-01-06T07:02:50Z
ddc:
- '040'
department:
- _id: '63'
- _id: '26'
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T08:16:44Z
date_updated: 2018-03-15T08:16:44Z
file_id: '1252'
file_name: 601-Kempkes-PhD.pdf
file_size: 3805310
relation: main_file
success: 1
file_date_updated: 2018-03-15T08:16:44Z
has_accepted_license: '1'
intvolume: ' 302'
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_identifier:
isbn:
- 978-3-942647-21-2
publisher: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
series_title: Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn
status: public
supervisor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
title: Local strategies for robot formation problems
type: dissertation
user_id: '5786'
volume: 302
year: '2012'
...
---
_id: '618'
author:
- first_name: Sven
full_name: Kurras, Sven
last_name: Kurras
citation:
ama: Kurras S. Distributed Sampling of Regular Graphs. Universität Paderborn;
2012.
apa: Kurras, S. (2012). Distributed Sampling of Regular Graphs. Universität
Paderborn.
bibtex: '@book{Kurras_2012, title={Distributed Sampling of Regular Graphs}, publisher={Universität
Paderborn}, author={Kurras, Sven}, year={2012} }'
chicago: Kurras, Sven. Distributed Sampling of Regular Graphs. Universität
Paderborn, 2012.
ieee: S. Kurras, Distributed Sampling of Regular Graphs. Universität Paderborn,
2012.
mla: Kurras, Sven. Distributed Sampling of Regular Graphs. Universität Paderborn,
2012.
short: S. Kurras, Distributed Sampling of Regular Graphs, Universität Paderborn,
2012.
date_created: 2017-10-17T12:42:52Z
date_updated: 2022-01-06T07:02:55Z
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: Distributed Sampling of Regular Graphs
type: mastersthesis
user_id: '15504'
year: '2012'
...
---
_id: '619'
abstract:
- lang: eng
text: 'Dynamics in networks is caused by a variety of reasons, like nodes moving
in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer
networks, evolution in social networks, and many others. In order to understand
such kinds of dynamics, and to design distributed algorithms that behave well
under dynamics, many ways to model dynamics are introduced and analyzed w.r.t.
correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman
have introduced a very general, worst case type model of dynamics: The edge set
of the network may change arbitrarily from step to step, the only restriction
is that it is connected at all times and the set of nodes does not change. An
extended model demands that a xed connected subnetwork is maintained over each
time interval of length T (T-interval dynamics). They have presented, among others,
algorithms for counting the number of nodes under such general models of dynamics.In
this paper, we generalize their models and algorithms by adding random edge faults,
i.e., we consider fault-prone dynamic networks: We assume that an edge currently
existing may fail to transmit data with some probability p. We rst observe that
strong counting, i.e., each node knows the correct count and stops, is not possible
in a model with random edge faults. Our main two positive results are feasibility
and runtime bounds for weak counting, i.e., stopping is no longer required (but
still a correct count in each node), and for strong counting with an upper bound,
i.e., an upper bound N on n is known to all nodes.'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Brandes P, Meyer auf der Heide F. Distributed Computing in Fault-Prone Dynamic
Networks. In: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic
Distributed Systems (TADDS). ICPS. ; 2012:9-14. doi:10.1145/2414815.2414818'
apa: Brandes, P., & Meyer auf der Heide, F. (2012). Distributed Computing in
Fault-Prone Dynamic Networks. In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS) (pp. 9–14). https://doi.org/10.1145/2414815.2414818
bibtex: '@inproceedings{Brandes_Meyer auf der Heide_2012, series={ICPS}, title={Distributed
Computing in Fault-Prone Dynamic Networks}, DOI={10.1145/2414815.2414818},
booktitle={Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)}, author={Brandes, Philipp and Meyer auf der Heide, Friedhelm},
year={2012}, pages={9–14}, collection={ICPS} }'
chicago: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” In Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 9–14. ICPS, 2012. https://doi.org/10.1145/2414815.2414818.
ieee: P. Brandes and F. Meyer auf der Heide, “Distributed Computing in Fault-Prone
Dynamic Networks,” in Proceedings of the 4th Workshop on Theoretical Aspects
of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.
mla: Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing
in Fault-Prone Dynamic Networks.” Proceedings of the 4th Workshop on Theoretical
Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14, doi:10.1145/2414815.2414818.
short: 'P. Brandes, F. Meyer auf der Heide, in: Proceedings of the 4th Workshop
on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.'
date_created: 2017-10-17T12:42:52Z
date_updated: 2022-01-06T07:02:56Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2414815.2414818
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:47:15Z
date_updated: 2018-03-15T06:47:15Z
file_id: '1244'
file_name: 619-Brandes_MadHTADDS12_01.pdf
file_size: 346044
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:47:15Z
has_accepted_license: '1'
page: 9-14
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 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)
series_title: ICPS
status: public
title: Distributed Computing in Fault-Prone Dynamic Networks
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '625'
abstract:
- lang: eng
text: 'This paper initiates the study of self-adjusting distributed data structures
for networks. In particular, we present SplayNets: a binary search tree based
network that is self-adjusting to routing request.We derive entropy bounds on
the amortized routing cost and show that our splaying algorithm has some interesting
properties.'
author:
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Chen
full_name: Avin, Chen
last_name: Avin
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Bernhard
full_name: Häupler, Bernhard
last_name: Häupler
- first_name: Zvi
full_name: Lotker, Zvi
last_name: Lotker
citation:
ama: 'Schmid S, Avin C, Scheideler C, Häupler B, Lotker Z. Brief Announcement: SplayNets
- Towards Self-Adjusting Distributed Data Structures. In: Proceedings of the
26th International Symposium on Distributed Computing (DISC). LNCS. ; 2012:439-440.
doi:10.1007/978-3-642-33651-5_47'
apa: 'Schmid, S., Avin, C., Scheideler, C., Häupler, B., & Lotker, Z. (2012).
Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.
In Proceedings of the 26th International Symposium on Distributed Computing
(DISC) (pp. 439–440). https://doi.org/10.1007/978-3-642-33651-5_47'
bibtex: '@inproceedings{Schmid_Avin_Scheideler_Häupler_Lotker_2012, series={LNCS},
title={Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data
Structures}, DOI={10.1007/978-3-642-33651-5_47},
booktitle={Proceedings of the 26th International Symposium on Distributed Computing
(DISC)}, author={Schmid, Stefan and Avin, Chen and Scheideler, Christian and Häupler,
Bernhard and Lotker, Zvi}, year={2012}, pages={439–440}, collection={LNCS} }'
chicago: 'Schmid, Stefan, Chen Avin, Christian Scheideler, Bernhard Häupler, and
Zvi Lotker. “Brief Announcement: SplayNets - Towards Self-Adjusting Distributed
Data Structures.” In Proceedings of the 26th International Symposium on Distributed
Computing (DISC), 439–40. LNCS, 2012. https://doi.org/10.1007/978-3-642-33651-5_47.'
ieee: 'S. Schmid, C. Avin, C. Scheideler, B. Häupler, and Z. Lotker, “Brief Announcement:
SplayNets - Towards Self-Adjusting Distributed Data Structures,” in Proceedings
of the 26th International Symposium on Distributed Computing (DISC), 2012,
pp. 439–440.'
mla: 'Schmid, Stefan, et al. “Brief Announcement: SplayNets - Towards Self-Adjusting
Distributed Data Structures.” Proceedings of the 26th International Symposium
on Distributed Computing (DISC), 2012, pp. 439–40, doi:10.1007/978-3-642-33651-5_47.'
short: 'S. Schmid, C. Avin, C. Scheideler, B. Häupler, Z. Lotker, in: Proceedings
of the 26th International Symposium on Distributed Computing (DISC), 2012, pp.
439–440.'
date_created: 2017-10-17T12:42:53Z
date_updated: 2022-01-06T07:02:58Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-642-33651-5_47
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:44:09Z
date_updated: 2018-03-15T06:44:09Z
file_id: '1240'
file_name: 625-disc12adjBAshort.pdf
file_size: 717284
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:44:09Z
has_accepted_license: '1'
page: 439-440
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 26th International Symposium on Distributed Computing
(DISC)
series_title: LNCS
status: public
title: 'Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures'
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '626'
abstract:
- lang: eng
text: The design of ecient search structures for peer-to-peer systems has attracted
a lot of attention in recent years. In this announcement we address the problem
of nding the predecessor in a key set and present an ecient data structure called
hashed Predecessor Patricia trie. Our hashed Predecessor Patricia trie supports
PredecessorSearch(x) and Insert(x) and Delete(x) in O(log log u) hash table accesses
when u is the size of the universe of the keys. That is the costs only depend
on u and not the size of the data structure. One feature of our approach is that
it only uses the lookup interface of the hash table and therefore hash table accesses
may be realized by any distributed hash table (DHT).
author:
- first_name: Sebastian
full_name: Kniesburges, Sebastian
last_name: Kniesburges
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Kniesburges S, Scheideler C. Brief Announcement: Hashed Predecessor Patricia
Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.
In: Proceedings of the 26th International Symposium on Distributed Computing
(DISC). LNCS. ; 2012:435-436. doi:10.1007/978-3-642-33651-5_45'
apa: 'Kniesburges, S., & Scheideler, C. (2012). Brief Announcement: Hashed Predecessor
Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer
Systems. In Proceedings of the 26th International Symposium on Distributed
Computing (DISC) (pp. 435–436). https://doi.org/10.1007/978-3-642-33651-5_45'
bibtex: '@inproceedings{Kniesburges_Scheideler_2012, series={LNCS}, title={Brief
Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient
Predecessor Queries in Peer-to-Peer Systems}, DOI={10.1007/978-3-642-33651-5_45},
booktitle={Proceedings of the 26th International Symposium on Distributed Computing
(DISC)}, author={Kniesburges, Sebastian and Scheideler, Christian}, year={2012},
pages={435–436}, collection={LNCS} }'
chicago: 'Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement:
Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor
Queries in Peer-to-Peer Systems.” In Proceedings of the 26th International
Symposium on Distributed Computing (DISC), 435–36. LNCS, 2012. https://doi.org/10.1007/978-3-642-33651-5_45.'
ieee: 'S. Kniesburges and C. Scheideler, “Brief Announcement: Hashed Predecessor
Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer
Systems,” in Proceedings of the 26th International Symposium on Distributed
Computing (DISC), 2012, pp. 435–436.'
mla: 'Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement: Hashed
Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries
in Peer-to-Peer Systems.” Proceedings of the 26th International Symposium on
Distributed Computing (DISC), 2012, pp. 435–36, doi:10.1007/978-3-642-33651-5_45.'
short: 'S. Kniesburges, C. Scheideler, in: Proceedings of the 26th International
Symposium on Distributed Computing (DISC), 2012, pp. 435–436.'
date_created: 2017-10-17T12:42:54Z
date_updated: 2022-01-06T07:02:59Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-642-33651-5_45
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:42:40Z
date_updated: 2018-03-15T06:42:40Z
file_id: '1239'
file_name: 626-Predecessor-Kniesburges_Scheideler.pdf
file_size: 184095
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:42:40Z
has_accepted_license: '1'
page: 435-436
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 26th International Symposium on Distributed Computing
(DISC)
series_title: LNCS
status: public
title: 'Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for
Efficient Predecessor Queries in Peer-to-Peer Systems'
type: conference
user_id: '15504'
year: '2012'
...