Tiara: A self-stabilizing deterministic skip list and skip graph

被引：16
作者：
Clouser, Thomas [1 ]
Nesterenko, Mikhail [1 ]
Scheideler, Christian [2 ]
机构：
[1] Kent State Univ, Dept Comp Sci, Kent, OH 44242 USA
[2] Tech Univ Munich, Inst Comp Sci, D-8046 Garching, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2012年 / 428卷
关键词：
Peer-to-peer networks; Overlay networks; Self-stabilization; PROTOCOL; SYSTEMS;
D O I：
10.1016/j.tcs.2011.12.079
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present Tiara a self-stabilizing peer-to-peer network maintenance algorithm. Tiara is truly deterministic which allows it to achieve exact performance bounds. Tiara allows logarithmic searches and topology updates. It is based on a novel sparse 0-1 skip list. We then describe its extension to a ringed structure and to a skip-graph. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：18 / 35
页数：18
相关论文
共 63 条
  • [1] Afek Y., 1997, Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, DOI 10.1145/259380.259505
  • [2] Albrecht K, 2006, LECT NOTES COMPUT SC, V4028, P275
  • [3] Alima L.O., 2004, LECT NOTES COMPUTER, V3460
  • [4] Andersen D., 2001, Operating Systems Review, V35, P131, DOI 10.1145/502059.502048
  • [5] Angluin D., 2005, P 17 ANN ACM S PAR A, P145, DOI DOI 10.1145/1073970.1073991
  • [6] [Anonymous], 2005, Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05
  • [7] [Anonymous], P SPAA
  • [8] Aspnes J, 2003, SIAM PROC S, P384
  • [9] Aspnes J, 2007, LECT NOTES COMPUT SC, V4878, P286
  • [10] Skip Graphs
    Aspnes, James
    Shah, Gauri
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)
1234567