{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:55:56Z","timestamp":1760151356678,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,3,18]],"date-time":"2022-03-18T00:00:00Z","timestamp":1647561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this work, we propose D3-Tree, a dynamic distributed deterministic structure for data management in decentralized networks, by engineering and extending an existing decentralized structure. Conducting an extensive experimental study, we verify that the implemented structure outperforms other well-known hierarchical tree-based structures since it provides better complexities regarding load-balancing operations. More specifically, the structure achieves an O(logN) amortized bound (N is the number of nodes present in the network), using an efficient deterministic load-balancing mechanism, which is general enough to be applied to other hierarchical tree-based structures. Moreover, our structure achieves O(logN) worst-case search performance. Last but not least, we investigate the structure\u2019s fault tolerance, which hasn\u2019t been sufficiently tackled in previous work, both theoretically and through rigorous experimentation. We prove that D3-Tree is highly fault-tolerant and achieves O(logN) amortized search cost under massive node failures, accompanied by a significant success rate. Afterwards, by incorporating this novel balancing scheme into the ART (Autonomous Range Tree) structure, we go one step further to achieve sub-logarithmic complexity and propose the ART+ structure. ART+ achieves an O(logb2logN) communication cost for query and update operations (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(loglogN) expected WHP (with high proability) number of hops and performs load-balancing in O(loglogN) amortized cost.<\/jats:p>","DOI":"10.3390\/a15030096","type":"journal-article","created":{"date-parts":[[2022,3,20]],"date-time":"2022-03-20T21:25:00Z","timestamp":1647811500000},"page":"96","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1825-5565","authenticated-orcid":false,"given":"Spyros","family":"Sioutas","sequence":"first","affiliation":[{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9783-1905","authenticated-orcid":false,"given":"Efrosini","family":"Sourla","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Tsichlas","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9555-4775","authenticated-orcid":false,"given":"Gerasimos","family":"Vonitsanos","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1425-5138","authenticated-orcid":false,"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patras, Greece"},{"name":"Computer Technology Institute & Press \u201cDiophantus\u201d, 26504 Patras, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,18]]},"reference":[{"key":"ref_1","unstructured":"Schollmeier, R. (2001, January 27\u201329). A Definition of Peer-to-Peer Networking for the Classification of Peer-to-Peer Architectures and Applications. Proceedings of the 1st International Conference on Peer-to-Peer Computing, Link\u00f6ping, Sweden."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ozsu, M.T., and Valduriez, P. (2011). Principles of Distributed Database Systems, Springer.","DOI":"10.1007\/978-1-4419-8834-8"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/1944339.1944343","article-title":"Load Balancing and Range Queries in P2P Systems Using P-Ring","volume":"10","author":"Crainiceanu","year":"2011","journal-title":"ACM Trans. Internet Technol."},{"key":"ref_4","unstructured":"Gupta, A., Agrawal, D., and Abbadi, A.E. (2003, January 5\u20138). Approximate Range Selection Queries in Peer-to-Peer Systems. Proceedings of the 1st Biennial Conference on Innovative Data Systems Research (CIDR 2003), Asilomar, CA, USA."},{"key":"ref_5","unstructured":"Sahin, O., Gupta, A., Agrawal, D., and Abbadi, A.E. (2004, January 2). A peer-to-peer framework for caching range queries. Proceedings of the 20th Conference on Data Engineering (ICDE 2004), Boston, MA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Bhargava, A., Kothapalli, K., Riley, C., Scheideler, C., and Thober, M. (2004). Pagoda: A Dynamic Overlay Network for Routing, Data Management, and Multicasting. SPAA \u201904, Proceedings of the 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Barcelona, Spain, 27\u201330 June 2004, ACM.","DOI":"10.1145\/1007912.1007938"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1007\/978-3-642-02930-1_47","article-title":"A Distributed and Oblivious Heap","volume":"Volume 5556","author":"Scheideler","year":"2009","journal-title":"Automata, Languages and Programming"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.jpdc.2021.11.004","article-title":"FMapper: Scalable read mapper based on succinct hash index on SunWay TaihuLight","volume":"161","author":"Xu","year":"2022","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_9","unstructured":"Jagadish, H.V., Ooi, B.C., and Vu, Q.H. (September, January 30). BATON: A Balanced Tree Structure for Peer-to-Peer Networks. Proceedings of the 31st Conference on Very Large Databases (VLDB \u201905), Trondheim, Norway."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Jagadish, H.V., Ooi, B.C., Tan, K., Vu, Q.H., and Zhang, R. (2006, January 27\u201329). Speeding up Search in P2P Networks with a Multi-way Tree Structure. Proceedings of the ACM International Conference on Management of Data (SIGMOD 2006), Chicago, IL, USA.","DOI":"10.1145\/1142473.1142475"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Papadopoulos, A.N., Sioutas, S., Zaroliagis, C.D., and Zacharatos, N. (2019, January 14\u201317). Efficient Distributed Range Query Processing in Apache Spark. Proceedings of the 19th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2019, Larnaca, Cyprus.","DOI":"10.1109\/CCGRID.2019.00073"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"104465","DOI":"10.1016\/j.ic.2019.104465","article-title":"Dynamic Interpolation Search revisited","volume":"270","author":"Kaporis","year":"2020","journal-title":"Inf. Comput."},{"key":"ref_13","unstructured":"Gupta, R., and Shen, X. (2020). Non-blocking interpolation search trees with doubly-logarithmic running time. PPoPP \u201920: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, USA, 22\u201326 February 2020, ACM."},{"key":"ref_14","first-page":"122","article-title":"Scalable and Hierarchical Distributed Data Structures for Efficient Big Data Management","volume":"Volume 12041","author":"Sioutas","year":"2019","journal-title":"Algorithmic Aspects of Cloud Computin-5th International Symposium, ALGOCLOUD 2019, Munich, Germany, 10 September 2019"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Brodal, G., Sioutas, S., Tsichlas, K., and Zaroliagis, C. (2014). D2-Tree: A New Overlay with Deterministic Bounds. International Symposium on Algorithms and Computation, Springer.","DOI":"10.1007\/s00453-014-9878-4"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/964723.383071","article-title":"Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications","volume":"31","author":"Stoica","year":"2001","journal-title":"SIGCOMM Comput. Commun. Rev."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10619-012-7112-4","article-title":"ART: Sub-Logarithmic Decentralized Range Query Processing with Probabilistic Guarantees","volume":"31","author":"Sioutas","year":"2012","journal-title":"J. Distrib. Parallel Databases (DAPD)"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sioutas, S., Sourla, E., Tsichlas, K., and Zaroliagis, C. (2015, January 14\u201316). D3-Tree: A Dynamic Deterministic Decentralized Structure. Proceedings of the Algorithms-ESA 2015-23rd Annual European Symposium, Patras, Greece. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-662-48350-3_82"},{"key":"ref_19","unstructured":"Sioutas, S., Sourla, E., Tsichlas, K., and Zaroliagis, C. (2015, January 14\u201315). ART+: A Fault-Tolerant Decentralized Tree Structure with Ultimate Sub-logarithmic Efficiency. Proceedings of the Algorithms-ALGOCLOUD 2015-1st International Workshop on Algorithmic Aspects of Cloud Computing, Patras, Greece. Lecture Notes in Computer Science."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kaporis, A., Makris, C., Sioutas, S., Tsakalidis, A., Tsichlas, K., and Zaroliagis, C. (2003, January 16\u201319). Improved bounds for finger search on a ram. Proceedings of the 11th Annual European Symposium on Algorithms (ESA), Budapest, Hungary.","DOI":"10.1007\/978-3-540-39658-1_31"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Sioutas, S., Papaloukopoulos, G., Sakkopoulos, E., Tsichlas, K., and Manolopoulos, Y. (2009). A novel Distributed P2P Simulator Architecture: D-P2P-Sim. CIKM \u201909, Proceedings of the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China, 2\u20136 November 2009, ACM CIKM.","DOI":"10.1145\/1645953.1646305"},{"key":"ref_22","first-page":"18","article-title":"Fuzzy Randomized Load Balancing for Cloud Computing","volume":"Volume 343","author":"Barolli","year":"2021","journal-title":"Advances on P2P, Parallel, Grid, Cloud and Internet Computing-Proceedings of the 16th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2021, Fukuoka, Japan, 28\u201330 October 2021"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ren, Y., and Parmer, G. (2019, January 9\u201313). Scalable Data-structures with Hierarchical, Distributed Delegation. Proceedings of the 20th International Middleware Conference, Middleware 2019, Davis, CA, USA.","DOI":"10.1145\/3361525.3361537"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Moualkia, Y., Amad, M., and Baadache, A. (2021). Hierarchical and scalable peer-to-peer architecture for online social network. J. King Saud Univ.-Comput. Inf. Sci., in press.","DOI":"10.1016\/j.jksuci.2021.04.009"},{"key":"ref_25","first-page":"1009","article-title":"Distributed arrays: An algebra for generic distributed query processing","volume":"39","author":"Behr","year":"2021","journal-title":"Distrib. Parallel Databases"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1007\/s10619-021-07326-1","article-title":"PatchIndex: Exploiting approximate constraints in distributed databases","volume":"39","author":"Sattler","year":"2021","journal-title":"Distrib. Parallel Databases"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s10619-020-07305-y","article-title":"In-memory parallelization of join queries over large ontological hierarchies","volume":"39","author":"Bilidas","year":"2021","journal-title":"Distrib. Parallel Databases"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1109\/TPDS.2021.3096076","article-title":"Decentralized edge intelligence: A dynamic resource allocation framework for hierarchical federated learning","volume":"33","author":"Lim","year":"2021","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TPDS.2021.3090759","article-title":"Efficient Distributed Approaches to Core Maintenance on Large Dynamic Graphs","volume":"33","author":"Weng","year":"2021","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/96\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:39:15Z","timestamp":1760135955000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,18]]},"references-count":29,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030096"],"URL":"https:\/\/doi.org\/10.3390\/a15030096","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,3,18]]}}}