---
_id: '243'
abstract:
- lang: eng
text: This paper introduces the problem of communication pattern adaption for a
distributed self-adjusting binary search tree. We propose a simple local algorithm,
which is closely related to the nearly thirty-year-old idea of splay trees and
evaluate its adaption performance in the distributed scenario if different communication
patterns are provided.To do so, the process of self-adjustment is modeled similarly
to a basic network creation game, in which the nodes want to communicate with
only a certain subset of all nodes. We show that, in general, the game (i.e.,
the process of local adjustments) does not converge, and convergence is related
to certain structures of the communication interests, which we call conflicts.We
classify conflicts and show that for two communication scenarios in which convergence
is guaranteed, the self-adjusting tree performs well.Furthermore, we investigate
the different classes of conflicts separately and show that, for a certain class
of conflicts, the performance of the tree network is asymptotically as good as
the performance for converging instances. However, for the other conflict classes,
a distributed self-adjusting binary search tree adapts poorly.
author:
- first_name: Thim Frederik
full_name: Strothmann, Thim Frederik
id: '11319'
last_name: Strothmann
citation:
ama: 'Strothmann TF. The impact of communication patterns on distributed locally
self-adjusting binary search trees. In: *Proceedings of the 9th International
Workshop on Algorithms and Computation (WALCOM)*. LNCS. ; 2015:175--186. doi:10.1007/978-3-319-15612-5_16'
apa: Strothmann, T. F. (2015). The impact of communication patterns on distributed
locally self-adjusting binary search trees. In *Proceedings of the 9th International
Workshop on Algorithms and Computation (WALCOM)* (pp. 175--186). https://doi.org/10.1007/978-3-319-15612-5_16
bibtex: '@inproceedings{Strothmann_2015, series={LNCS}, title={The impact of communication
patterns on distributed locally self-adjusting binary search trees}, DOI={10.1007/978-3-319-15612-5_16},
booktitle={Proceedings of the 9th International Workshop on Algorithms and Computation
(WALCOM)}, author={Strothmann, Thim Frederik}, year={2015}, pages={175--186},
collection={LNCS} }'
chicago: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed
Locally Self-Adjusting Binary Search Trees.” In *Proceedings of the 9th International
Workshop on Algorithms and Computation (WALCOM)*, 175--186. LNCS, 2015. https://doi.org/10.1007/978-3-319-15612-5_16.
ieee: T. F. Strothmann, “The impact of communication patterns on distributed locally
self-adjusting binary search trees,” in *Proceedings of the 9th International
Workshop on Algorithms and Computation (WALCOM)*, 2015, pp. 175--186.
mla: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed
Locally Self-Adjusting Binary Search Trees.” *Proceedings of the 9th International
Workshop on Algorithms and Computation (WALCOM)*, 2015, pp. 175--186, doi:10.1007/978-3-319-15612-5_16.
short: 'T.F. Strothmann, in: Proceedings of the 9th International Workshop on Algorithms
and Computation (WALCOM), 2015, pp. 175--186.'
date_created: 2017-10-17T12:41:39Z
date_updated: 2022-01-06T06:56:17Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.1007/978-3-319-15612-5_16
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-21T09:59:00Z
date_updated: 2018-03-21T09:59:00Z
file_id: '1495'
file_name: 243-Strothmann-Walcom2015.pdf
file_size: 1003113
relation: main_file
success: 1
file_date_updated: 2018-03-21T09:59:00Z
has_accepted_license: '1'
language:
- iso: eng
page: 175--186
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 Workshop on Algorithms and Computation
(WALCOM)
series_title: LNCS
status: public
title: The impact of communication patterns on distributed locally self-adjusting
binary search trees
type: conference
user_id: '477'
year: '2015'
...