---
_id: '5762'
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
    that is closely related to the over thirty-year-old idea of splay trees and evaluate
    its adaption performance in the distributed scenario if different communication
    patterns are provided. \r\nTo 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. \r\nWe show that, in general, the game
    (i.e., the process of local adjustments) does not converge, and that convergence
    is related to certain structures of the communication interests, which we call
    conflicts. \r\nWe classify conflicts and show that for two communication scenarios
    in which convergence is guaranteed, the self-adjusting tree performs well. \r\nFurthermore,
    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.\r\nHowever, 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 Self-Adjusting
    Binary Search Tree. <i>Journal of Graph Algorithms and Applications</i>. 2016;20(1):79-100.
    doi:<a href="https://doi.org/10.7155/jgaa.00385">10.7155/jgaa.00385</a>
  apa: Strothmann, T. F. (2016). The Impact of Communication Patterns on Distributed
    Self-Adjusting Binary Search Tree. <i>Journal of Graph Algorithms and Applications</i>,
    <i>20</i>(1), 79–100. <a href="https://doi.org/10.7155/jgaa.00385">https://doi.org/10.7155/jgaa.00385</a>
  bibtex: '@article{Strothmann_2016, title={The Impact of Communication Patterns on
    Distributed Self-Adjusting Binary Search Tree}, volume={20}, DOI={<a href="https://doi.org/10.7155/jgaa.00385">10.7155/jgaa.00385</a>},
    number={1}, journal={Journal of Graph Algorithms and Applications}, publisher={Journal
    of Graph Algorithms and Applications}, author={Strothmann, Thim Frederik}, year={2016},
    pages={79–100} }'
  chicago: 'Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed
    Self-Adjusting Binary Search Tree.” <i>Journal of Graph Algorithms and Applications</i>
    20, no. 1 (2016): 79–100. <a href="https://doi.org/10.7155/jgaa.00385">https://doi.org/10.7155/jgaa.00385</a>.'
  ieee: T. F. Strothmann, “The Impact of Communication Patterns on Distributed Self-Adjusting
    Binary Search Tree,” <i>Journal of Graph Algorithms and Applications</i>, vol.
    20, no. 1, pp. 79–100, 2016.
  mla: Strothmann, Thim Frederik. “The Impact of Communication Patterns on Distributed
    Self-Adjusting Binary Search Tree.” <i>Journal of Graph Algorithms and Applications</i>,
    vol. 20, no. 1, Journal of Graph Algorithms and Applications, 2016, pp. 79–100,
    doi:<a href="https://doi.org/10.7155/jgaa.00385">10.7155/jgaa.00385</a>.
  short: T.F. Strothmann, Journal of Graph Algorithms and Applications 20 (2016) 79–100.
date_created: 2018-11-19T15:33:50Z
date_updated: 2022-01-06T07:02:38Z
ddc:
- '040'
department:
- _id: '79'
doi: 10.7155/jgaa.00385
file:
- access_level: closed
  content_type: application/pdf
  creator: thim
  date_created: 2018-11-27T11:58:08Z
  date_updated: 2018-11-27T11:58:08Z
  file_id: '5912'
  file_name: Strothmann2016.20.1.pdf
  file_size: 2324066
  relation: main_file
  success: 1
file_date_updated: 2018-11-27T11:58:08Z
has_accepted_license: '1'
intvolume: '        20'
issue: '1'
language:
- iso: eng
page: 79-100
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Journal of Graph Algorithms and Applications
publication_identifier:
  issn:
  - 1526-1719
publication_status: published
publisher: Journal of Graph Algorithms and Applications
quality_controlled: '1'
status: public
title: The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search
  Tree
type: journal_article
user_id: '477'
volume: 20
year: '2016'
...