Change search
ReferencesLink to record
Permanent link

Direct link
Distributed k-ary System: Algorithms for Distributed Hash Tables
KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
2006 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness.

Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast.

We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries.

Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f.

The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described.

Place, publisher, year, edition, pages
Stockholm: KTH , 2006. , xv, 193 p.
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 06:09
Keyword [en]
distributed hash tables, structured overlay networks, distributed algorithms, distributed systems, group communication, replication
National Category
Computer Science
URN: urn:nbn:se:kth:diva-4186OAI: diva2:11131
Public defence
2006-12-07, F3, Lindstedtsvägen 26, campus Valhallavägen, Stockholm, 13:00
QC 20100824Available from: 2006-11-23 Created: 2006-11-23 Last updated: 2010-08-24Bibliographically approved

Open Access in DiVA

fulltext(1597 kB)274 downloads
File information
File name FULLTEXT01.pdfFile size 1597 kBChecksum SHA-1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Ghodsi, Ali
By organisation
Microelectronics and Information Technology, IMIT
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 274 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 652 hits
ReferencesLink to record
Permanent link

Direct link