Brief Announcement: SplayNets Towards Self-Adjusting Distributed Data Structures

被引：0
|
作者：
Schmid, Stefan [1 ]
Avin, Chen [2 ]
Scheideler, Christian [3 ]
Haeupler, Bernhard [4 ]
Lotker, Zvi
机构：
[1] TU Berlin, Berlin, Germany
[2] BGU, Beer Sheva, Israel
[3] Univ Paderborn, D-33098 Paderborn, Germany
[4] MIT, Cambridge, MA 02139 USA
来源：
DISTRIBUTED COMPUTING, DISC 2012 | 2012年 / 7611卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：439 / +
页数：2
相关论文
共 50 条
  • [1] SELF-ADJUSTING DATA-STRUCTURES
    LIAO, AM
    DR DOBBS JOURNAL, 1990, 15 (02): : 44 - &
  • [2] Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation
    Acar, Umut A.
    Aksenov, Vitaly
    Westrick, Sam
    PROCEEDINGS OF THE 29TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'17), 2017, : 275 - 277
  • [3] UNSUCCESSFUL SEARCH IN SELF-ADJUSTING DATA-STRUCTURES
    HUI, LCK
    MARTEL, C
    JOURNAL OF ALGORITHMS, 1993, 15 (03) : 447 - 481
  • [4] Distributed Self-Adjusting Tree Networks
    Peres, Bruna Soares
    Souza, Otavio Augusto de Oliveira
    Goussevskaia, Olga
    Avin, Chen
    Schmid, Stefan
    IEEE TRANSACTIONS ON CLOUD COMPUTING, 2023, 11 (01) : 716 - 729
  • [5] Distributed Self-Adjusting Tree Networks
    Peres, Bruna
    Souza, Otavio A. de O.
    Goussevskaia, Olga
    Avin, Chen
    Schmid, Stefan
    IEEE CONFERENCE ON COMPUTER COMMUNICATIONS (IEEE INFOCOM 2019), 2019, : 145 - 153
  • [6] Smooth Heaps and a Dual View of Self-Adjusting Data Structures
    Kozma, Laszlo
    Saranurak, Thatchaphol
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 801 - 814
  • [7] SMOOTH HEAPS AND A DUAL VIEW OF SELF-ADJUSTING DATA STRUCTURES
    Kozma, Laszlo
    Saranurak, Thatchaphol
    SIAM JOURNAL ON COMPUTING, 2020, 49 (05)
  • [8] STRUCTURES OF SELF-ADJUSTING SYSTEMS WITH MODELS
    ELISEEV, VD
    AUTOMATION AND REMOTE CONTROL, 1976, 37 (02) : 209 - 216
  • [9] Randomized distributed self-adjusting tree networks
    Souza, Otavio A. de O.
    Caldeira, Caio A.
    Goussevskaia, Olga
    COMPUTER NETWORKS, 2023, 235
  • [10] Study on self-adjusting property and self-adjusting structures for planar Crank-Rocker mechanism
    An, PW
    Huang, ML
    Du, L
    He, Z
    ELEVENTH WORLD CONGRESS IN MECHANISM AND MACHINE SCIENCE, VOLS 1-5, PROCEEDINGS, 2004, : 1199 - 1203
12345