---
_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'
...
---
_id: '632'
abstract:
- lang: eng
text: 'Given an integer h, a graph G = (V;E) with arbitrary positive edge capacities
and k pairs of vertices (s1; t1); (s2; t2); : : : ; (sk; tk), called terminals,
an h-route cut is a set F µ E of edges such that after the removal of the edges
in F no pair si ¡ ti is connected by h edge-disjoint paths (i.e., the connectivity
of every si ¡ ti pair is at most h ¡ 1 in (V;E n F)). The h-route cut is a natural
generalization of the classical cut problem for multicommodity °ows (take h =
1). The main result of this paper is an O(h722h log2 k)-approximation algorithm
for the minimum h-route cut problem in the case that s1 = s2 = ¢ ¢ ¢ = sk, called
the single source case. As a corollary of it we obtain an approximate duality
theorem for multiroute multicom-modity °ows and cuts with a single source. This
partially answers an open question posted in several previous papers dealing with
cuts for multicommodity multiroute problems.'
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. Approximate Duality of Multicommodity Multiroute Flows
and Cuts: Single Source Case. In: Proceedings of the 23th ACM SIAM Symposium
on Discrete Algorithms (SODA). ; 2012:800-810. doi:10.1137/1.9781611973099.64'
apa: 'Kolman, P., & Scheideler, C. (2012). Approximate Duality of Multicommodity
Multiroute Flows and Cuts: Single Source Case. In Proceedings of the 23th ACM
SIAM Symposium on Discrete Algorithms (SODA) (pp. 800–810). https://doi.org/10.1137/1.9781611973099.64'
bibtex: '@inproceedings{Kolman_Scheideler_2012, title={Approximate Duality of Multicommodity
Multiroute Flows and Cuts: Single Source Case}, DOI={10.1137/1.9781611973099.64},
booktitle={Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)},
author={Kolman, Petr and Scheideler, Christian}, year={2012}, pages={800–810}
}'
chicago: 'Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity
Multiroute Flows and Cuts: Single Source Case.” In Proceedings of the 23th
ACM SIAM Symposium on Discrete Algorithms (SODA), 800–810, 2012. https://doi.org/10.1137/1.9781611973099.64.'
ieee: 'P. Kolman and C. Scheideler, “Approximate Duality of Multicommodity Multiroute
Flows and Cuts: Single Source Case,” in Proceedings of the 23th ACM SIAM Symposium
on Discrete Algorithms (SODA), 2012, pp. 800–810.'
mla: 'Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity
Multiroute Flows and Cuts: Single Source Case.” Proceedings of the 23th ACM
SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 800–10, doi:10.1137/1.9781611973099.64.'
short: 'P. Kolman, C. Scheideler, in: Proceedings of the 23th ACM SIAM Symposium
on Discrete Algorithms (SODA), 2012, pp. 800–810.'
date_created: 2017-10-17T12:42:55Z
date_updated: 2022-01-06T07:03:01Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1137/1.9781611973099.64
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:35:58Z
date_updated: 2018-03-15T06:35:58Z
file_id: '1234'
file_name: 632-SODA2012-Scheideler_01.pdf
file_size: 220213
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:35:58Z
has_accepted_license: '1'
page: 800-810
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 23th ACM SIAM Symposium on Discrete Algorithms (SODA)
status: public
title: 'Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source
Case'
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '640'
abstract:
- lang: eng
text: Small-world networks have received significant attention because of their
potential as models for the interaction networks of complex systems. Specifically,
neither random networks nor regular lattices seem to be an adequate framework
within which to study real-world complex systems such as chemical-reaction networks,
neural networks, food webs, social networks, scientific-collaboration networks,
and computer networks. Small-world networks provide some desired properties like
an expected polylogarithmic distance between two processes in the network, which
allows routing in polylogarithmic hops by simple greedy routing, and robustness
against attacks or failures. By these properties, small-world networks are possible
solutions for large overlay networks comparable to structured overlay networks
like CAN, Pastry, Chord, which also provide polylogarithmic routing, but due to
their uniform structure, structured overlay networks are more vulnerable to attacks
or failures. In this paper we bring together a randomized process converging to
a small-world network and a self-stabilization process so that a small-world network
is formed out of any weakly connected initial state. To the best of our knowledge
this is the first distributed self-stabilization process for building a small-world
network.
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 Self-Stabilization Process
for Small-World Networks. In: Proceedings of the 26th IEEE International Parallel
and Distributed Processing Symposium (IPDPS). ; 2012:1261--1271. doi:10.1109/IPDPS.2012.115'
apa: Kniesburges, S., Koutsopoulos, A., & Scheideler, C. (2012). A Self-Stabilization
Process for Small-World Networks. In Proceedings of the 26th IEEE International
Parallel and Distributed Processing Symposium (IPDPS) (pp. 1261--1271). https://doi.org/10.1109/IPDPS.2012.115
bibtex: '@inproceedings{Kniesburges_Koutsopoulos_Scheideler_2012, title={A Self-Stabilization
Process for Small-World Networks}, DOI={10.1109/IPDPS.2012.115},
booktitle={Proceedings of the 26th IEEE International Parallel and Distributed
Processing Symposium (IPDPS)}, author={Kniesburges, Sebastian and Koutsopoulos,
Andreas and Scheideler, Christian}, year={2012}, pages={1261--1271} }'
chicago: Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler.
“A Self-Stabilization Process for Small-World Networks.” In Proceedings of
the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
1261--1271, 2012. https://doi.org/10.1109/IPDPS.2012.115.
ieee: S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “A Self-Stabilization
Process for Small-World Networks,” in Proceedings of the 26th IEEE International
Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 1261--1271.
mla: Kniesburges, Sebastian, et al. “A Self-Stabilization Process for Small-World
Networks.” Proceedings of the 26th IEEE International Parallel and Distributed
Processing Symposium (IPDPS), 2012, pp. 1261--1271, doi:10.1109/IPDPS.2012.115.
short: 'S. Kniesburges, A. Koutsopoulos, C. Scheideler, in: Proceedings of the 26th
IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012,
pp. 1261--1271.'
date_created: 2017-10-17T12:42:56Z
date_updated: 2022-01-06T07:03:04Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1109/IPDPS.2012.115
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T14:13:13Z
date_updated: 2018-03-14T14:13:13Z
file_id: '1230'
file_name: 640-IPDPS2012-Kniesb-Kouts-Scheideler.pdf
file_size: 210176
relation: main_file
success: 1
file_date_updated: 2018-03-14T14:13:13Z
has_accepted_license: '1'
page: 1261--1271
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 IEEE International Parallel and Distributed Processing
Symposium (IPDPS)
status: public
title: A Self-Stabilization Process for Small-World Networks
type: conference
user_id: '15504'
year: '2012'
...
---
_id: '1868'
author:
- first_name: Andr{\'{e}}a
full_name: W. Richa, Andr{\'{e}}a
last_name: W. Richa
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jin
full_name: Zhang, Jin
last_name: Zhang
citation:
ama: W. Richa A, Scheideler C, Schmid S, Zhang J. Competitive throughput in multi-hop
wireless networks despite adaptive jamming. Distributed Computing. 2013;(3):159--171.
doi:10.1007/s00446-012-0180-x
apa: W. Richa, A., Scheideler, C., Schmid, S., & Zhang, J. (2013). Competitive
throughput in multi-hop wireless networks despite adaptive jamming. Distributed
Computing, (3), 159--171. https://doi.org/10.1007/s00446-012-0180-x
bibtex: '@article{W. Richa_Scheideler_Schmid_Zhang_2013, title={Competitive throughput
in multi-hop wireless networks despite adaptive jamming}, DOI={10.1007/s00446-012-0180-x},
number={3}, journal={Distributed Computing}, author={W. Richa, Andr{\’{e}}a and
Scheideler, Christian and Schmid, Stefan and Zhang, Jin}, year={2013}, pages={159--171}
}'
chicago: 'W. Richa, Andr{\’{e}}a, Christian Scheideler, Stefan Schmid, and Jin Zhang.
“Competitive Throughput in Multi-Hop Wireless Networks despite Adaptive Jamming.”
Distributed Computing, no. 3 (2013): 159--171. https://doi.org/10.1007/s00446-012-0180-x.'
ieee: A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang, “Competitive throughput
in multi-hop wireless networks despite adaptive jamming,” Distributed Computing,
no. 3, pp. 159--171, 2013.
mla: W. Richa, Andr{\’{e}}a, et al. “Competitive Throughput in Multi-Hop Wireless
Networks despite Adaptive Jamming.” Distributed Computing, no. 3, 2013,
pp. 159--171, doi:10.1007/s00446-012-0180-x.
short: A. W. Richa, C. Scheideler, S. Schmid, J. Zhang, Distributed Computing (2013)
159--171.
date_created: 2018-03-28T06:31:02Z
date_updated: 2022-01-06T06:53:50Z
department:
- _id: '79'
doi: 10.1007/s00446-012-0180-x
issue: '3'
page: 159--171
publication: Distributed Computing
status: public
title: Competitive throughput in multi-hop wireless networks despite adaptive jamming
type: journal_article
user_id: '15504'
year: '2013'
...
---
_id: '1870'
author:
- first_name: Rizal
full_name: Mohd Nor, Rizal
last_name: Mohd Nor
- first_name: Mikhail
full_name: Nesterenko, Mikhail
last_name: Nesterenko
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: Mohd Nor R, Nesterenko M, Scheideler C. Corona: A stabilizing deterministic
message-passing skip list. Theor Comput Sci. 2013:119--129. doi:10.1016/j.tcs.2012.08.029
apa: Mohd Nor, R., Nesterenko, M., & Scheideler, C. (2013). Corona: A stabilizing
deterministic message-passing skip list. Theor. Comput. Sci., 119--129.
https://doi.org/10.1016/j.tcs.2012.08.029
bibtex: '@article{Mohd Nor_Nesterenko_Scheideler_2013, title={Corona: A stabilizing
deterministic message-passing skip list}, DOI={10.1016/j.tcs.2012.08.029},
journal={Theor. Comput. Sci.}, author={Mohd Nor, Rizal and Nesterenko, Mikhail
and Scheideler, Christian}, year={2013}, pages={119--129} }'
chicago: Mohd Nor, Rizal, Mikhail Nesterenko, and Christian Scheideler. “Corona:
A Stabilizing Deterministic Message-Passing Skip List.” Theor. Comput. Sci.,
2013, 119--129. https://doi.org/10.1016/j.tcs.2012.08.029.
ieee: R. Mohd Nor, M. Nesterenko, and C. Scheideler, “Corona: A stabilizing deterministic
message-passing skip list,” Theor. Comput. Sci., pp. 119--129, 2013.
mla: Mohd Nor, Rizal, et al. “Corona: A Stabilizing Deterministic Message-Passing
Skip List.” Theor. Comput. Sci., 2013, pp. 119--129, doi:10.1016/j.tcs.2012.08.029.
short: R. Mohd Nor, M. Nesterenko, C. Scheideler, Theor. Comput. Sci. (2013) 119--129.
date_created: 2018-03-28T06:32:26Z
date_updated: 2022-01-06T06:53:51Z
department:
- _id: '79'
doi: 10.1016/j.tcs.2012.08.029
page: 119--129
publication: Theor. Comput. Sci.
status: public
title: 'Corona: A stabilizing deterministic message-passing skip list'
type: journal_article
user_id: '15504'
year: '2013'
...
---
_id: '1871'
author:
- first_name: Andrea
full_name: W. Richa, Andrea
last_name: W. Richa
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jin
full_name: Zhang, Jin
last_name: Zhang
citation:
ama: W. Richa A, Scheideler C, Schmid S, Zhang J. An Efficient and Fair MAC Protocol
Robust to Reactive Interference. IEEE/ACM Trans Netw. 2013;(3):760--771.
doi:10.1109/TNET.2012.2210241
apa: W. Richa, A., Scheideler, C., Schmid, S., & Zhang, J. (2013). An Efficient
and Fair MAC Protocol Robust to Reactive Interference. IEEE/ACM Trans. Netw.,
(3), 760--771. https://doi.org/10.1109/TNET.2012.2210241
bibtex: '@article{W. Richa_Scheideler_Schmid_Zhang_2013, title={An Efficient and
Fair MAC Protocol Robust to Reactive Interference}, DOI={10.1109/TNET.2012.2210241},
number={3}, journal={IEEE/ACM Trans. Netw.}, author={W. Richa, Andrea and Scheideler,
Christian and Schmid, Stefan and Zhang, Jin}, year={2013}, pages={760--771} }'
chicago: 'W. Richa, Andrea, Christian Scheideler, Stefan Schmid, and Jin Zhang.
“An Efficient and Fair MAC Protocol Robust to Reactive Interference.” IEEE/ACM
Trans. Netw., no. 3 (2013): 760--771. https://doi.org/10.1109/TNET.2012.2210241.'
ieee: A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang, “An Efficient and Fair
MAC Protocol Robust to Reactive Interference,” IEEE/ACM Trans. Netw., no.
3, pp. 760--771, 2013.
mla: W. Richa, Andrea, et al. “An Efficient and Fair MAC Protocol Robust to Reactive
Interference.” IEEE/ACM Trans. Netw., no. 3, 2013, pp. 760--771, doi:10.1109/TNET.2012.2210241.
short: A. W. Richa, C. Scheideler, S. Schmid, J. Zhang, IEEE/ACM Trans. Netw. (2013)
760--771.
date_created: 2018-03-28T06:32:59Z
date_updated: 2022-01-06T06:53:51Z
department:
- _id: '79'
doi: 10.1109/TNET.2012.2210241
issue: '3'
page: 760--771
publication: IEEE/ACM Trans. Netw.
status: public
title: An Efficient and Fair MAC Protocol Robust to Reactive Interference
type: journal_article
user_id: '15504'
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. Theory of Computing Systems. 2013;(2):341-363.
doi:10.1007/s00224-013-9454-3'
apa: 'Kolman, P., & Scheideler, C. (2013). Towards Duality of Multicommodity
Multiroute Cuts and Flows: Multilevel Ball-Growing. Theory of Computing Systems,
(2), 341–363. https://doi.org/10.1007/s00224-013-9454-3'
bibtex: '@article{Kolman_Scheideler_2013, title={Towards Duality of Multicommodity
Multiroute Cuts and Flows: Multilevel Ball-Growing}, DOI={10.1007/s00224-013-9454-3},
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.” Theory of Computing Systems,
no. 2 (2013): 341–63. https://doi.org/10.1007/s00224-013-9454-3.'
ieee: 'P. Kolman and C. Scheideler, “Towards Duality of Multicommodity Multiroute
Cuts and Flows: Multilevel Ball-Growing,” Theory of Computing Systems,
no. 2, pp. 341–363, 2013.'
mla: 'Kolman, Petr, and Christian Scheideler. “Towards Duality of Multicommodity
Multiroute Cuts and Flows: Multilevel Ball-Growing.” Theory of Computing Systems,
no. 2, Springer, 2013, pp. 341–63, doi:10.1007/s00224-013-9454-3.'
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: '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: Proceedings of the 27th IEEE International Parallel and
Distributed Processing Symposium (IPDPS). ; 2013:395-406. doi:10.1109/IPDPS.2013.40'
apa: Avin, C., Häupler, B., Lotker, Z., Scheideler, C., & Schmid, S. (2013).
Locally Self-Adjusting Tree Networks. In Proceedings of the 27th IEEE International
Parallel and Distributed Processing Symposium (IPDPS) (pp. 395–406). https://doi.org/10.1109/IPDPS.2013.40
bibtex: '@inproceedings{Avin_Häupler_Lotker_Scheideler_Schmid_2013, title={Locally
Self-Adjusting Tree Networks}, DOI={10.1109/IPDPS.2013.40},
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 Proceedings of the 27th
IEEE International Parallel and Distributed Processing Symposium (IPDPS),
395–406, 2013. https://doi.org/10.1109/IPDPS.2013.40.
ieee: C. Avin, B. Häupler, Z. Lotker, C. Scheideler, and S. Schmid, “Locally Self-Adjusting
Tree Networks,” in Proceedings of the 27th IEEE International Parallel and
Distributed Processing Symposium (IPDPS), 2013, pp. 395–406.
mla: Avin, Chen, et al. “Locally Self-Adjusting Tree Networks.” Proceedings of
the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS),
2013, pp. 395–406, doi:10.1109/IPDPS.2013.40.
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: '519'
abstract:
- lang: eng
text: In this work we present the first scalable distributed information system,i.e.,
a system with low storage overhead, that is provably robust againstDenial-of-Service
(DoS) attacks by a current insider. We allow acurrent insider to have complete
knowledge about the information systemand to have the power to block any \epsilon-fraction
of its serversby a DoS-attack, where \epsilon can be chosen up to a constant.
The taskof the system is to serve any collection of lookup requests with at most
oneper non-blocked server in an efficient way despite this attack. Previously,scalable
solutions were only known for DoS-attacks of past insiders, where apast insider
only has complete knowledge about some past time pointt_0 of the information system.
Scheideler et al. (DISC 2007, SPAA 2009) showedthat in this case it is possible
to design an information system so that anyinformation that was inserted or last
updated after t_0 is safe against a DoS-attack. But their constructions would
not work at all for a current insider. The key idea behindour IRIS system is to
make extensive use of coding. More precisely, we presenttwo alternative distributed
coding strategies with an at most logarithmicstorage overhead that can handle
up to a constant fraction of blocked servers.
author:
- first_name: Martina
full_name: Eikel, Martina
last_name: Eikel
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Eikel M, Scheideler C. IRIS: A Robust Information System Against Insider DoS-Attacks.
In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). ; 2013:119-129. doi:10.1145/2486159.2486186'
apa: 'Eikel, M., & Scheideler, C. (2013). IRIS: A Robust Information System
Against Insider DoS-Attacks. In Proceedings of the 25th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA) (pp. 119–129). https://doi.org/10.1145/2486159.2486186'
bibtex: '@inproceedings{Eikel_Scheideler_2013, title={IRIS: A Robust Information
System Against Insider DoS-Attacks}, DOI={10.1145/2486159.2486186},
booktitle={Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Eikel, Martina and Scheideler, Christian},
year={2013}, pages={119–129} }'
chicago: 'Eikel, Martina, and Christian Scheideler. “IRIS: A Robust Information
System Against Insider DoS-Attacks.” In Proceedings of the 25th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), 119–29, 2013. https://doi.org/10.1145/2486159.2486186.'
ieee: 'M. Eikel and C. Scheideler, “IRIS: A Robust Information System Against Insider
DoS-Attacks,” in Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 2013, pp. 119–129.'
mla: 'Eikel, Martina, and Christian Scheideler. “IRIS: A Robust Information System
Against Insider DoS-Attacks.” Proceedings of the 25th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA), 2013, pp. 119–29, doi:10.1145/2486159.2486186.'
short: 'M. Eikel, C. Scheideler, in: Proceedings of the 25th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA), 2013, pp. 119–129.'
date_created: 2017-10-17T12:42:33Z
date_updated: 2022-01-06T07:01:42Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1145/2486159.2486186
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:38:34Z
date_updated: 2018-03-15T10:38:34Z
file_id: '1299'
file_name: 519-iris-spaa2013_01.pdf
file_size: 554618
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:38:34Z
has_accepted_license: '1'
page: 119-129
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
status: public
title: 'IRIS: A Robust Information System Against Insider DoS-Attacks'
type: conference
user_id: '15504'
year: '2013'
...
---
_id: '542'
abstract:
- lang: eng
text: 'We consider the problem of managing a dynamic heterogeneous storagesystem
in a distributed way so that the amount of data assigned to a hostin that system
is related to its capacity. Two central problems have to be solvedfor this: (1)
organizing the hosts in an overlay network with low degree and diameterso that
one can efficiently check the correct distribution of the data androute between
any two hosts, and (2) distributing the data among the hosts so thatthe distribution
respects the capacities of the hosts and can easily be adapted asthe set of hosts
or their capacities change. We present distributed protocols forthese problems
that are self-stabilizing and that do not need any global knowledgeabout the system
such as the number of nodes or the overall capacity of thesystem. Prior to this
work no solution was known satisfying these properties.'
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. CONE-DHT: A distributed self-stabilizing
algorithm for a heterogeneous storage system. In: Proceedings of the 27th International
Symposium on Distributed Computing (DISC). LNCS. ; 2013:537-549. doi:10.1007/978-3-642-41527-2_37'
apa: 'Kniesburges, S., Koutsopoulos, A., & Scheideler, C. (2013). CONE-DHT:
A distributed self-stabilizing algorithm for a heterogeneous storage system. In
Proceedings of the 27th International Symposium on Distributed Computing (DISC)
(pp. 537–549). https://doi.org/10.1007/978-3-642-41527-2_37'
bibtex: '@inproceedings{Kniesburges_Koutsopoulos_Scheideler_2013, series={LNCS},
title={CONE-DHT: A distributed self-stabilizing algorithm for a heterogeneous
storage system}, DOI={10.1007/978-3-642-41527-2_37},
booktitle={Proceedings of the 27th International Symposium on Distributed Computing
(DISC)}, author={Kniesburges, Sebastian and Koutsopoulos, Andreas and Scheideler,
Christian}, year={2013}, pages={537–549}, collection={LNCS} }'
chicago: 'Kniesburges, Sebastian, Andreas Koutsopoulos, and Christian Scheideler.
“CONE-DHT: A Distributed Self-Stabilizing Algorithm for a Heterogeneous Storage
System.” In Proceedings of the 27th International Symposium on Distributed
Computing (DISC), 537–49. LNCS, 2013. https://doi.org/10.1007/978-3-642-41527-2_37.'
ieee: 'S. Kniesburges, A. Koutsopoulos, and C. Scheideler, “CONE-DHT: A distributed
self-stabilizing algorithm for a heterogeneous storage system,” in Proceedings
of the 27th International Symposium on Distributed Computing (DISC), 2013,
pp. 537–549.'
mla: 'Kniesburges, Sebastian, et al. “CONE-DHT: A Distributed Self-Stabilizing Algorithm
for a Heterogeneous Storage System.” Proceedings of the 27th International
Symposium on Distributed Computing (DISC), 2013, pp. 537–49, doi:10.1007/978-3-642-41527-2_37.'
short: 'S. Kniesburges, A. Koutsopoulos, C. Scheideler, in: Proceedings of the 27th
International Symposium on Distributed Computing (DISC), 2013, pp. 537–549.'
date_created: 2017-10-17T12:42:38Z
date_updated: 2022-01-06T07:01:53Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-642-41527-2_37
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T10:32:48Z
date_updated: 2018-03-15T10:32:48Z
file_id: '1289'
file_name: 542-CONE-DHT_A_distributed_self-stabilizing_algorithm_for_a_heterogeneous_storage_system.pdf
file_size: 262302
relation: main_file
success: 1
file_date_updated: 2018-03-15T10:32:48Z
has_accepted_license: '1'
page: 537-549
project:
- _id: '1'
name: SFB 901
- _id: '13'
name: SFB 901 - Subprojekt C1
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 27th International Symposium on Distributed Computing
(DISC)
series_title: LNCS
status: public
title: 'CONE-DHT: A distributed self-stabilizing algorithm for a heterogeneous storage
system'
type: conference
user_id: '15504'
year: '2013'
...