Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
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
Identifiers
URN: urn:nbn:se:kth:diva-4186OAI: oai:DiVA.org:kth-4186DiVA: diva2:11131
Public defence
2006-12-07, F3, Lindstedtsvägen 26, campus Valhallavägen, Stockholm, 13:00
Opponent
Supervisors
Note
QC 20100824Available from: 2006-11-23 Created: 2006-11-23 Last updated: 2010-08-24Bibliographically approved

Open Access in DiVA

fulltext(1597 kB)343 downloads
File information
File name FULLTEXT01.pdfFile size 1597 kBChecksum MD5
a8e1f48f30ae9be43774683451ce2bc18c1289dea46e5aa055c6c213be76562d9bfe456a
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: 343 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

urn-nbn

Altmetric score

urn-nbn
Total: 679 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf