Hide
Раскрыть

ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Russian version: ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

Alexander Ponomarenko 1, Yury Malkov 2, Andrey Logvinov 3, Vladimir Krylov  4
  • 1 National Research University Higher School of Economics, 30 Sormovskoye Highway, Nizhny Novgorod, 603014, Russian Federation
  • 2 Institute of Applied Physics of the Russian Academy of Sciences , 46, Ulyanova Street, Nizhny Novgorod, 603950, Russian Federation
  • 3 MERA Labs LLC , 192, Rodionova Street, Nizhny Novgorod, 603093, Russian Federation
  • 4 Nizhny Novgorod State Technical University , 24 Minina Street, Nizhny Novgorod, 603950, Russian Federation

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

2016. No. 1(35). P. 26–36 [issue contents]

Alexander A. Ponomarenko - Researcher, Laboratory of Algorithms and Technologies for Network Analysis National Research University Higher School of Economics  
Address: 136, Rodionova Street, Nizhny Novgorod, 603093, Russian Federation 
E-mail: aponomarenko@hse.ru

Yury A. Malkov - Junior Research Fellow,The Institute of Applied Physics of the Russian Academy of Sciences
Address: 46, Ulyanova Street, Nizhny Novgorod, 603950, Russian Federation
 E-mail: yurymalkov@mail.ru

Andrey A. Logvinov - Project Leader, MERA Labs LLC
Address: 192, Rodionova Street, Nizhny Novgorod, 603093, Russian Federation 
E-mail: alogvinov@meralabs.com

Vladimir V. Krylov - Professor, Head of Big Data Laboratory Nizhny Novgorod State Technical University
Address: 24 Minina Street, Nizhny Novgorod, 603950, Russian Federation 
E-mail: vkrylov@heterarchica.com

      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. 

Citation: Ponomarenko A.A., Malkov Yu.A., Logvinov A.A., Krylov V.V. (2016) An overlay network for distributed exact and range search in one-dimensional space. Business Informatics, no. 1 (35), pp. 26–36.  DOI: 10.17323/1998-0663.2016.1.26.36.
BiBTeX
RIS
 
 
Rambler's Top100 rss