---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Thim Frederik
foaf_name: Strothmann, Thim Frederik
foaf_surname: Strothmann
foaf_workInfoHomepage: http://www.librecat.org/personId=11319
bibo_doi: 10.1007/978-3-319-15612-5_16
dct_date: 2015^xs_gYear
dct_language: eng
dct_title: The impact of communication patterns on distributed locally self-adjusting
binary search trees@
...