ART $$^+$$ + : A Fault-Tolerant Decentralized Tree Structure with Ultimate Sub-logarithmic Efficiency
| Autor: | Kostas Tsichlas, Efrosini Sourla, Spyros Sioutas, Christos D. Zaroliagis |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Algorithmic Aspects of Cloud Computing ISBN: 9783319299181 ALGOCLOUD |
| DOI: | 10.1007/978-3-319-29919-8_10 |
| Popis: | In this paper, we focus on large-scale, decentralized environments. Our aim is to develop an architecture that can support range queries and scale in terms of number of nodes as well as of data items stored. The solutions proposed in literature are inadequate for our purposes, since their classic logarithmic complexity is too expensive even for single queries. In this work, we contribute the ART$$^+$$+ Autonomous Range Tree structure, which outperforms the most popular decentralized structures, since it achieves sub-logarithmic complexity. ART$$^+$$+ achieves an $$O\log _b^2{\log {N}}$$Ologb2logN communication cost for query and update operations, where b is a double-exponentially power of 2 and N is the total number of nodes. Moreover, ART$$^+$$+ is a fully dynamic and fault-tolerant structure, which supports the join/leave node operations in $$O\log {\log {N}}$$OloglogN expected w.h.p number of hops and performs load-balancing in $$O\log {\log {N}}$$OloglogN amortized cost. The theoretical performance is verified through experiments. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|