BATON

BATON: a balanced tree structure for peer-to-peer networks. We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries can be answered in O(log N) steps and also that update operations (to both data and network) have an amortized cost of O(log N). An experimental assessment validates the practicality of our proposal.

This software is also peer reviewed by journal TOMS.


References in zbMATH (referenced in 23 articles )

Showing results 1 to 20 of 23.
Sorted by year (citations)

1 2 next

  1. Ferrucci, L.; Ricci, L.; Albano, M.; Baraglia, R.; Mordacchini, M.: Multidimensional range queries on hierarchical Voronoi overlays (2016)
  2. Brodal, Gerth Stølting; Sioutas, Spyros; Tsichlas, Kostas; Zaroliagis, Christos: $D^2$-tree: a new overlay with deterministic bounds (2015)
  3. Izumi, Taisuke; Izumi, Tomoko; Ono, Hirotaka; Wada, Koichi: Approximability of minimum certificate dispersal with tree structures (2015)
  4. Sioutas, Spyros; Sourla, Efrosini; Tsichlas, Kostas; Zaroliagis, Christos: $D^3$-tree: a dynamic deterministic decentralized structure (2015)
  5. Lee, Jongwuk; Kim, Jinhan; Hwang, Seung-won: Supporting efficient distributed skyline computation using skyline views (2012) ioport
  6. Qiao, Ying; v.Bochmann, Gregor: Load balancing in peer-to-peer systems using a diffusive approach (2012) ioport
  7. Qiao, Ying; von Bochmann, Gregor: Load balancing in peer-to-peer systems using a diffusive approach (2012)
  8. Tsatsanifos, George; Samoladas, Vasilis: A novel robust on-line protocol for load-balancing in structured peer-to-peer systems (2012) ioport
  9. Tsatsanifos, George; Samoladas, Vasilis: A novel robust on-line protocol for load-balancing in structured peer-to-peer systems (2012)
  10. Aekaterinidis, Ioannis; Triantafillou, Peter: Pyracanthus: a scalable solution for DHT-independent content-based publish/subscribe data networks (2011) ioport
  11. Izumi, Taisuke; Gradinariu Potop-Butucaru, Maria; Valero, Mathieu: Physical expander in virtual tree overlay (2011)
  12. Li, Ruixuan; Song, Wei; Shen, Haiying; Xiao, Weijun; Lu, Zhengding: A flabellate overlay network for multi-attribute search (2011) ioport
  13. Zhang, Yiming; Lu, Xicheng; Li, Dongsheng: Survey of DHT topology construction techniques in virtual computing environments (2011)
  14. Ke, Xu; Meina, Song; Junde, Song: An improved P2P lookup protocol model (2010) ioport
  15. Sánchez-Artigas, Marc; García López, Pedro: Echo: a peer-to-peer clustering framework for improving communication in DHTs (2010)
  16. Cui, Bin; Xu, Linhao; Zhao, Jiakui: Linking identical neighborly partitions for efficient high-dimensional similarity search in unstructured peer-to-peer systems (2009) ioport
  17. Doulkeridis, Christos; Vlachou, Akrivi; Kotidis, Yannis; Vazirgiannis, Michalis: Efficient range query processing in metric spaces over highly distributed data (2009) ioport
  18. du Mouza, Cédric; Litwin, Witold; Rigaux, Philippe: Large-scale indexing of spatial data in distributed repositories: the SD-Rtree (2009) ioport
  19. Wang, Shiyuan; Vu, Quang Hieu; Ooi, Beng Chin; Tung, Anthony K.H.; Xu, Lizhen: Skyframe: a framework for skyline query processing in peer-to-peer systems (2009) ioport
  20. Narayanan, Dushyanth; Donnelly, Austin; Mortier, Richard; Rowstron, Antony: Delay aware querying with seaweed (2008) ioport

1 2 next