The impact of communication patterns on distributed locally self-adjusting binary search trees

T.F. Strothmann, in: Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM), 2015, pp. 175--186.

Download
Restricted 243-Strothmann-Walcom2015.pdf 1.00 MB
Conference Paper | English
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.
Publishing Year
Proceedings Title
Proceedings of the 9th International Workshop on Algorithms and Computation (WALCOM)
Page
175--186
LibreCat-ID

Cite this

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
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
@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} }
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.
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.
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.
Main File(s)
File Name
243-Strothmann-Walcom2015.pdf 1.00 MB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T09:59:00Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar