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

DOI10.1016/J.TCS.2011.12.079zbMath1263.68026OpenAlexW2034021369MaRDI QIDQ418743

Christian Scheideler, Thomas Clouser, Mikhail V. Nesterenko

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.079

zbMATH Keywords

self-stabilizationpeer-to-peer networksoverlay networksdistributed skip graph

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Information storage and retrieval of data (68P20) Distributed systems (68M14) Network protocols (68M12) Internet topics (68M11)

Related Items (11)

A self-stabilizing Hashed Patricia Trie ⋮ Towards worst-case churn resistant peer-to-peer systems ⋮ Fair priority scheduling (FPS): a process scheduling algorithm based on skip ring data structure ⋮ Corona: a stabilizing deterministic message-passing skip list ⋮ Re-Chord: a self-stabilizing chord overlay network ⋮ A note on the parallel runtime of self-stabilizing graph linearization ⋮ Towards a universal approach for the finite departure problem in overlay networks ⋮ Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs ⋮ Towards a Universal Approach for the Finite Departure Problem in Overlay Networks ⋮ Self-stabilizing metric graphs ⋮ Study on massive-scale slow-hash recovery using unified probabilistic context-free grammar and symmetrical collaborative prioritization with parallel machines

Uses Software

• Chord
• Pastry
• UNITY

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Corona: a stabilizing deterministic message-passing skip list
• Stabilization-preserving atomicity refinement
• T-Man: Gossip-based fast overlay topology construction
• Robust random number generation for peer-to-peer systems
• An exercise in proving self-stabilization with a variant function
• Universal continuous routing strategies
• Self-stabilizing extensions for message-passing systems
• Concurrent maintenance of rings
• HyperTree for self-stabilizing peer-to-peer systems
• The expansion and mixing time of skip graphs with applications
• Self-stabilization by window washing
• Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization
• How to spread adversarial nodes?
• A Self-stabilizing and Local Delaunay Graph Construction
• A Scheme for Fast Parallel Communication
• Self-stabilizing systems in spite of distributed control
• Skip graphs
• A distributed polylogarithmic time algorithm for self-stabilizing skip graphs
• Viceroy
• On the topologies formed by selfish peers
• Linearization: Locally Self-Stabilizing Sorting in Graphs
• Parallel Processing and Applied Mathematics
• Self-stabilization by counter flushing
• Fault-local distributed mending (extended abstract)
• Time-adaptive self stabilization
• Automata, Languages and Programming

This page was built for publication: Tiara: a self-stabilizing deterministic skip list and skip graph