Knowledge base: Warsaw University of Technology

Settings and your account

Back

Optimization of efficiency and resilience to node failures of distributed hash tables

Artur Olszak

Abstract

In recent years, we observe a growing interest in large-scale distributed systems based on the distributed hash table algorithm (DHT). A DHT is a distributed system storing large amount of information in a way allowing efficient lookup for the information being stored. DHT systems are used to store key-value pairs, similarly to a hash table. However, the key-value pairs set is stored in a distributed manner and is shared among the nodes of the distributed hash table. Every node in the DHT maintains a list of references to other nodes in the system - a routing table. The routing table allows decreasing the distance left to the destination node in each lookup step (the distance between node identifiers, according to the chosen metric). The structure of the routing table, the choice of the metric defining logical distances between nodes, and the lookup algorithm have fundamental influence on the path lengths between nodes and the resilience of the system to node failures. The use of the one-dimensional model (placing the nodes logically on a ring) allows the nodes to maintain (in addition to neighbors providing efficient lookup) sets of “sequential neighbors” - certain numbers of neighbors that are the closest existing nodes in both directions on the ring. Such a model yields a very high level of resilience to node failures. This thesis presents a novel model of a distributed hash table based on a hierarchical hypercube geometry. The presented approach employs a variable multi-dimensional metric adopting the Steinhaus transform. It is shown that the new approach allows reaching a higher level of resilience to node failures, as well as a shorter average lookup path length than with the use of the sequential neighbors sets. The thesis describes the new DHT architecture and the processes of determining optimal solutions. Novel routing and lookup algorithms are discussed, as well as DHT resource management algorithms, routing table nodes selection algorithms, maintenance and recovery procedures, and solutions increasing security in the system. The work also presents the architecture of the implemented DHT library and the simulator that was used to evaluate the presented solutions. Individual design decisions are supported by results of extensive simulations and compared to the existing solutions.
Record ID
WUT8688c2472d2542339918db25331b5860
Diploma type
Doctor of Philosophy
Author
Artur Olszak Artur Olszak,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Title in Polish
Optymalizacja wydajności i odporności na awarie węzłów rozproszonej tablicy mieszającej
Title in English
Optimization of efficiency and resilience to node failures of distributed hash tables
Language
(en) English
Certifying Unit
Faculty of Electronics and Information Technology (FEIT)
Discipline
information science / (technology domain) / (technological sciences)
Status
Finished
Start date
26-02-2013
Defense Date
20-10-2015
Title date
27-10-2015
Supervisor
Internal reviewers
External reviewers
Marek Tudruj Marek Tudruj,, Undefined Affiliation
Pages
146
Keywords in English
distributed hash table, routing, lookup, resilience
Abstract in English
In recent years, we observe a growing interest in large-scale distributed systems based on the distributed hash table algorithm (DHT). A DHT is a distributed system storing large amount of information in a way allowing efficient lookup for the information being stored. DHT systems are used to store key-value pairs, similarly to a hash table. However, the key-value pairs set is stored in a distributed manner and is shared among the nodes of the distributed hash table. Every node in the DHT maintains a list of references to other nodes in the system - a routing table. The routing table allows decreasing the distance left to the destination node in each lookup step (the distance between node identifiers, according to the chosen metric). The structure of the routing table, the choice of the metric defining logical distances between nodes, and the lookup algorithm have fundamental influence on the path lengths between nodes and the resilience of the system to node failures. The use of the one-dimensional model (placing the nodes logically on a ring) allows the nodes to maintain (in addition to neighbors providing efficient lookup) sets of “sequential neighbors” - certain numbers of neighbors that are the closest existing nodes in both directions on the ring. Such a model yields a very high level of resilience to node failures. This thesis presents a novel model of a distributed hash table based on a hierarchical hypercube geometry. The presented approach employs a variable multi-dimensional metric adopting the Steinhaus transform. It is shown that the new approach allows reaching a higher level of resilience to node failures, as well as a shorter average lookup path length than with the use of the sequential neighbors sets. The thesis describes the new DHT architecture and the processes of determining optimal solutions. Novel routing and lookup algorithms are discussed, as well as DHT resource management algorithms, routing table nodes selection algorithms, maintenance and recovery procedures, and solutions increasing security in the system. The work also presents the architecture of the implemented DHT library and the simulator that was used to evaluate the presented solutions. Individual design decisions are supported by results of extensive simulations and compared to the existing solutions.
PKT classification
4100
KBN classification
28 Informatyka
EU classification
80-30
Thesis file

Uniform Resource Identifier
https://repo.pw.edu.pl/info/phd/WUT8688c2472d2542339918db25331b5860/
URN
urn:pw-repo:WUT8688c2472d2542339918db25331b5860

Confirmation
Are you sure?
Report incorrect data on this page