An overlay network for distributed exact and range search in one-dimensional space

Ponomarenko Alexander A., Malkov A., Logvinov Andrey A. and Krylov V.

Бизнес-информатика, 2016, issue 1 (35), 26-36

Abstract: The ability to scale is a desirable business requirement for computer systems. Distributed systems clearly demonstrate this ability and might to process very large volumes of data. Many systems with distributed architecture are based on the distributed hash table (DHT), which manages a set of distributed network nodes connected not only by a physical channel, but also by an additional overlay network. This overlay network is used for searching nodes and for distributing tasks among them. The main feature of this approach is that there is no central element or node which knows the global topology of the network. Nodes in the network are searched by passing a query message from one node to another. Despite that, every node has knowledge only about a small number of other nodes, and the network is organized in such a way that search involves a logarithmical number of nodes. There are several DHT implementations which specify how to construct and how to support the structure of the network. In this paper, we demonstrate the way in which such a network can be constructed much simpler by applying the sight modification of the recently published Metrized Small World algorithm to the case of one dimension. We provide a theoretical analysis for the case of uniform distribution and empirical analysis for other distributions. The main advantage of the proposed algorithm is that it is immutable to data distribution and does not need to support any particular distribution of the length. In addition, we show how to separate completely the concept of network location of data from the search functionality. This separation is important, for instance, for building global storages where data is owned by multiple parties and each party is interested in keeping control over the aspects of physical storage and access to the data it owns. So in contrast to DHT, insertion of new data does not require relocation to an existing node.

Keywords: ПОИСК БЛИЖАЙШЕГО СОСЕДА; NEAREST NEIGHBOR SEARCH; МЕТРИЧЕСКОЕ ПРОСТРАНСТВО; METRIC SPACE; РАСПРЕДЕЛЕННЫЕ ВЫЧИСЛЕНИЯ; DISTRIBUTED COMPUTING; ИНТЕРНЕТ-ТЕХНОЛОГИЯ И ПРИЛОЖЕНИЯ; INTERNET TECHNOLOGY AND APPLICATIONS; СТРУКТУРА ДАННЫХ; DATA STRUCTURE; АЛГОРИТМ; ALGORITHM (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
http://cyberleninka.ru/article/n/an-overlay-networ ... ne-dimensional-space

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:scn:025686:16532913

Access Statistics for this article

More articles in Бизнес-информатика from CyberLeninka, Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский университет «Высшая школа экономики»
Bibliographic data for series maintained by CyberLeninka ().