Brief Announcement: SplayNets Towards Self-Adjusting Distributed Data Structures
Stefan Schmid, Chen Avin, Christian Scheideler, Bernhard Haeupler, Zvi Lotker, Tu Berlin, U. Paderborn Germany · 2013
Abstract. This paper initiates the study of self-adjusting distributed data structures or networks. In particular, we present SplayNets: a binary search tree based network that is self-adjusting to the routing requests. We derive entropy bounds on the amortized routing cost and show that our splaying algorithm has some interesting properties. 1. Distributed Splay Trees. In the mid 80s, Sleator and Tarjan [1] introduced an appealing new paradigm to design efficient data structures: rather than optimizing traditional metrics such as the search tree depth in the worst-case, the authors proposed to make data structures self-adjusting and considered the amortized cost as the performance metric—the “average cost ” per operation for a given sequence s of lookups. The authors described splay trees, self-adjusting binary search trees in which frequently accessed elements are moved closer to the root, improving the average access times weighted by the elements ’ popularity. The popularity distribution must not be known in advance and may even change over time. We, in this paper, initiate the study of a distributed generalization of splay trees as a network. We consider a distributed data