You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 44.201.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 23:54, 31 July 2024.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪AntiCompositeNumber‬. The reason given is Open proxy/Webhost: Visit the FAQ if you are affected .
- Start of block: 13:55, 18 August 2022
- Expiry of block: 13:55, 18 April 2025
Your current IP address is 44.201.28.123. The blocked range is 44.201.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((Short description|Decentralized distributed system with lookup service))
((More citations needed|date=September 2020))
A '''distributed hash table''' ('''DHT''') is a [[Distributed computing|distributed system]] that provides a lookup service similar to a [[hash table]]. [[Key–value pair]]s are stored in a DHT, and any participating [[node (networking)|node]] can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. ''Keys'' are unique identifiers which map to particular ''values'', which in turn can be anything from addresses, to [[Electronic document|documents]], to arbitrary [[Data (computing)|data]].<ref name=StoicaEtAl2001>((Cite journal | last1 = Stoica | first1 = I. | author-link1 = Ion Stoica| last2 = Morris | first2 = R. | last3 = Karger | first3 = D. | author-link3 = David Karger| last4 = Kaashoek | first4 = M. F. | last5 = Balakrishnan | first5 = H. | author-link5 = Hari Balakrishnan| title = Chord: A scalable peer-to-peer lookup service for internet applications| doi = 10.1145/964723.383071 | journal = ACM SIGCOMM Computer Communication Review | volume = 31 | issue = 4 | pages = 149 | year = 2001 | url = http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf |quote=A value can be an address, a document, or an arbitrary data item. ))</ref> Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to [[scale (computing)|scale]] to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

DHTs form an infrastructure that can be used to build more complex services, such as [[anycast]], cooperative [[Web cache|web caching]], [[distributed file system]]s, [[Domain name system|domain name services]], [[instant messaging]], [[multicast]], and also [[peer-to-peer file sharing]] and [[content distribution]] systems. Notable distributed networks that use DHTs include [[BitTorrent (protocol)|BitTorrent]]'s distributed tracker, the [[Kad network]], the [[Storm botnet]], the [[Tox (protocol)|Tox instant messenger]], [[Freenet]], the [[YaCy]] search engine, and the [[InterPlanetary File System]].

[[File:DHT en.svg|500px|right|thumb|Distributed hash tables]]

== History ==
DHT research was originally motivated, in part, by [[peer-to-peer]] (P2P) systems such as [[Freenet]], [[Gnutella]], [[BitTorrent]] and [[Napster]], which took advantage of resources distributed across the Internet to provide a single useful application. In particular, they took advantage of increased [[Bandwidth (computing)|bandwidth]] and [[hard disk]] capacity to provide a file-sharing service.<ref>((cite journal |last1=Liz, Crowcroft|display-authors=et al |title=A survey and comparison of peer-to-peer overlay network schemes |journal=IEEE Communications Surveys & Tutorials |date=2005 |volume=7 |issue=2 |pages=72–93|doi=10.1109/COMST.2005.1610546 |citeseerx=10.1.1.109.6124 |s2cid=7971188 |url=http://www.cl.cam.ac.uk/teaching/2005/AdvSysTop/survey.pdf ))</ref>

These systems differed in how they located the data offered by their peers. Napster, the first large-scale P2P content delivery system, required a central index server: each node, upon joining, would send a list of locally held files to the server, which would perform searches and refer the queries to the nodes that held the results. This central component left the system vulnerable to attacks and lawsuits.

Gnutella and similar networks moved to a [[query flooding]] model((spaced ndash)) in essence, each search would result in a message being broadcast to every other machine in the network. While avoiding a [[single point of failure]], this method was significantly less efficient than Napster. Later versions of Gnutella clients moved to a [[dynamic querying]] model which vastly improved efficiency.<ref>((cite journal |last1=Richter, Stevenson|display-authors=et al |title=Analysis of the impact of dynamic querying models on client-server relationships |journal=Trends in Modern Computing |date=2009 |pages=682–701))</ref>

Freenet is fully distributed, but employs a [[Heuristic (computer science)|heuristic]] [[key-based routing]] in which each file is associated with a key, and files with similar keys tend to cluster on a similar set of nodes. Queries are likely to be routed through the network to such a cluster without needing to visit many peers.<ref>((citation |url=https://freenetproject.org/papers/lic.pdf |title=Searching in a Small World Chapters 1 & 2 |access-date=2012-01-10 |archive-date=2012-03-16 |archive-url=https://web.archive.org/web/20120316102141/https://freenetproject.org/papers/lic.pdf |url-status=dead ))</ref> However, Freenet does not guarantee that data will be found.

Distributed hash tables use a more structured key-based routing in order to attain both the decentralization of Freenet and Gnutella, and the efficiency and guaranteed results of Napster. One drawback is that, like Freenet, DHTs only directly support exact-match search, rather than keyword search, although Freenet's [[routing algorithm]] can be generalized to any key type where a closeness operation can be defined.<ref>((citation |chapter-url=https://freenetproject.org/papers/ddisrs.pdf |title=A Distributed Decentralized Information Storage and Retrieval System |chapter=Section 5.2.2 |access-date=2012-01-10 |archive-date=2012-03-16 |archive-url=https://web.archive.org/web/20120316102156/https://freenetproject.org/papers/ddisrs.pdf |url-status=dead ))</ref>

In 2001, four systems&mdash;[[Content addressable network|CAN]],<ref name = "Ratnasamy01">((cite journal |title=A Scalable Content-Addressable Network |publisher=In Proceedings of ACM SIGCOMM 2001 |author=Ratnasamy |year=2001 |url=http://www.eecs.berkeley.edu/~sylvia/papers/cans.pdf |access-date=2013-05-20|display-authors=etal))</ref> [[Chord (peer-to-peer)|Chord]],<ref>[[Hari Balakrishnan]], [[M. Frans Kaashoek]], David Karger, [[Robert Tappan Morris|Robert Morris]], and Ion Stoica. [http://www.cs.berkeley.edu/~istoica/papers/2003/cacm03.pdf Looking up data in P2P systems]. In [[Communications of the ACM]], February 2003.</ref> [[Pastry (DHT)|Pastry]], and [[Tapestry (DHT)|Tapestry]]&mdash;ignited DHTs as a popular research topic. 
A project called the Infrastructure for Resilient Internet Systems (Iris) was funded by a $12 million grant from the United States [[National Science Foundation]] in 2002.<ref>((Cite news |title= New P2P network funded by US government |author= David Cohen |work= New Scientist |date= October 1, 2002 |url= https://www.newscientist.com/article.ns?id=dn2861 |access-date= November 10, 2013 ))</ref>
Researchers included [[Sylvia Ratnasamy]], [[Ion Stoica]], [[Hari Balakrishnan]] and [[Scott Shenker]].<ref>((Cite news |title= MIT, Berkeley, ICSI, NYU, and Rice Launch the IRIS Project |work= Press release |publisher= MIT |date= September 25, 2002 |url= https://iris.pdos.csail.mit.edu/MITPressRelease1.doc |access-date= November 10, 2013 |url-status= dead |archive-url= https://web.archive.org/web/20150926070618/https://iris.pdos.csail.mit.edu/MITPressRelease1.doc |archive-date= September 26, 2015 ))</ref>
Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network.

== Properties ==
DHTs characteristically emphasize the following properties:

* [[Decentralized computing|Autonomy and decentralization]]: The nodes collectively form the system without any central coordination.
* [[Fault tolerance]]: The system should be reliable (in some sense) even with nodes continuously joining, leaving, and failing.<ref>R Mokadem, A Hameurlain and AM Tjoa. [https://www.irit.fr/~Riad.Mokadem/wp-content/uploads/sites/67/2020/12/Resource-discovery-service-while-minimizing-maintenance-overhead-in-hierarchical-DHT-systems-iiWas2010.pdf Resource discovery service while minimizing maintenance overhead in hierarchical DHT systems]. Proc. iiWas, 2010</ref>
* [[scale (computing)|Scalability]]: The system should function efficiently even with thousands or millions of nodes.

A key technique used to achieve these goals is that any one node needs to coordinate with only a few other nodes in the system – most commonly, [[Big O notation|O]](log ''n'') of the ''n'' participants (see below) – so that only a limited amount of work needs to be done for each change in membership.

Some DHT designs seek to be [[Secure communication|secure]] against malicious participants<ref>Guido Urdaneta, Guillaume Pierre and Maarten van Steen. [http://www.globule.org/publi/SDST_acmcs2009.html A Survey of DHT Security Techniques]. ACM Computing Surveys 43(2), January 2011.</ref> and to allow participants to remain [[Anonymity|anonymous]], though this is less common than in many other peer-to-peer (especially [[file sharing]]) systems; see [[anonymous P2P]].

== Structure ==
The structure of a DHT can be decomposed into several main components.<ref>Moni Naor and Udi Wieder. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/dh.pdf Novel Architectures for P2P Applications: the Continuous-Discrete Approach]. Proc. SPAA, 2003.</ref><ref>Gurmeet Singh Manku. [http://www-db.stanford.edu/~manku/phd/index.html Dipsea: A Modular Distributed Hash Table] ((webarchive|url=https://web.archive.org/web/20040910154927/http://www-db.stanford.edu/~manku/phd/index.html |date=2004-09-10 )). Ph. D. Thesis (Stanford University), August 2004.</ref> The foundation is an abstract [[Keyspace (distributed data store)|keyspace]], such as the set of 160-bit [[string (computer science)|string]]s. A keyspace [[Partition (database)|partitioning]] scheme splits ownership of this keyspace among the participating nodes. An [[overlay network]] then connects the nodes, allowing them to find the owner of any given key in the keyspace.

Once these components are in place, a typical use of the DHT for storage and retrieval might proceed as follows. Suppose the keyspace is the set of 160-bit strings. To index a file with given ((Var serif|filename)) and ((mvar|data)) in the DHT, the [[SHA-1]] hash of ((mvar|filename)) is generated, producing a 160-bit key ((mvar|k)), and a message ((math|''put''(''k, data''))) is sent to any node participating in the DHT. The message is forwarded from node to node through the overlay network until it reaches the single node responsible for key ((mvar|k)) as specified by the keyspace partitioning. That node then stores the key and the data. Any other client can then retrieve the contents of the file by again hashing ((mvar|filename)) to produce ((mvar|k)) and asking any DHT node to find the data associated with ((mvar|k)) with a message ((math|''get''(''k''))). The message will again be routed through the overlay to the node responsible for ((mvar|k)), which will reply with the stored ((mvar|data)).

The keyspace partitioning and overlay network components are described below with the goal of capturing the principal ideas common to most DHTs; many designs differ in the details.

=== Keyspace partitioning ===
Most DHTs use some variant of [[consistent hashing]] or [[rendezvous hashing]] to map keys to nodes. The two algorithms appear to have been devised independently and simultaneously to solve the distributed hash table problem.

Both consistent hashing and rendezvous hashing have the essential property that removal or addition of one node changes only the set of keys owned by the nodes with adjacent IDs, and leaves all other nodes unaffected. Contrast this with a traditional [[hash table]] in which addition or removal of one bucket causes nearly the entire keyspace to be remapped. Since any change in ownership typically corresponds to bandwidth-intensive movement of objects stored in the DHT from one node to another, minimizing such reorganization is required to efficiently support high rates of [[Churn rate|churn]] (node arrival and failure).

==== Consistent hashing ====
((further|Consistent hashing))

Consistent hashing employs a function <math>\delta(k_1, k_2)</math> that defines an abstract notion of the distance between the keys <math>k_1</math> and <math>k_2</math>, which is unrelated to geographical distance or [[network latency]]. Each node is assigned a single key called its ''identifier'' (ID). A node with ID <math>i_x</math> owns all the keys <math>k_m</math> for which <math>i_x</math> is the closest ID, measured according to <math>\delta(k_m, i_x)</math>.

For example, the [[Chord (peer-to-peer)|Chord DHT]] uses consistent hashing, which treats nodes as points on a circle, and <math>\delta(k_1, k_2)</math> is the distance traveling clockwise around the circle from <math>k_1</math> to <math>k_2</math>. Thus, the circular keyspace is split into contiguous segments whose endpoints are the node identifiers. If <math>i_1</math> and <math>i_2</math> are two adjacent IDs, with a shorter clockwise distance from <math>i_1</math> to <math>i_2</math>, then the node with ID <math>i_2</math> owns all the keys that fall between <math>i_1</math> and <math>i_2</math>.

==== Rendezvous hashing ====
((further|Rendezvous hashing))

In rendezvous hashing, also called highest random weight (HRW) hashing, all clients use the same hash function <math>h()</math> (chosen ahead of time) to associate a key to one of the ''n'' available servers.
Each client has the same list of identifiers ((math|((mset|''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub> )))), one for each server.
Given some key ''k'', a client computes ''n'' hash weights ((math|1=''w''<sub>1</sub> = ''h''(''S''<sub>1</sub>, ''k''), ''w''<sub>2</sub> = ''h''(''S''<sub>2</sub>, ''k''), ..., ''w''<sub>''n''</sub> = ''h''(''S''<sub>''n''</sub>, ''k''))).
The client associates that key with the server corresponding to the highest hash weight for that key.
A server with ID <math>S_x</math> owns all the keys <math>k_m</math> for which the hash weight <math>h(S_x, k_m)</math> is higher than the hash weight of any other node for that key.

==== Locality-preserving hashing ====
((further|Locality-preserving hashing))

Locality-preserving hashing ensures that similar keys are assigned to similar objects. This can enable a more efficient execution of range queries, however, in contrast to using consistent hashing, there is no more assurance that the keys (and thus the load) is uniformly randomly distributed over the key space and the participating peers. DHT protocols such as Self-Chord and Oscar<ref>((Cite journal|last1=Girdzijauskas|first1=Šarūnas|last2=Datta|first2=Anwitaman|last3=Aberer|first3=Karl|date=2010-02-01|title=Structured overlay for heterogeneous environments|journal=ACM Transactions on Autonomous and Adaptive Systems|volume=5|issue=1|pages=1–25|doi=10.1145/1671948.1671950|s2cid=13218263|issn=1556-4665|url=http://infoscience.epfl.ch/record/134972))</ref> address such issues. Self-Chord decouples object keys from peer IDs and sorts keys along the ring with a statistical approach based on the [[swarm intelligence]] paradigm.<ref>((cite journal |last1=Forestiero |first1=Agostino |last2=Leonardi |first2=Emilio |last3=Mastroianni |first3=Carlo |last4=Meo |first4=Michela |title=Self-Chord: A Bio-Inspired P2P Framework for Self-Organizing Distributed Systems |journal=IEEE/ACM Transactions on Networking |date=October 2010 |volume=18 |issue=5 |pages=1651–1664 |doi=10.1109/TNET.2010.2046745 |s2cid=14797120 |url=http://porto.polito.it/2370172/ ))</ref> Sorting ensures that similar keys are stored by neighbour nodes and that discovery procedures, including [[Range query (data structures)|range queries]], can be performed in logarithmic time. Oscar constructs a navigable [[small-world network]] based on [[random walk]] sampling also assuring logarithmic search time.

=== Overlay network ===
Each node maintains a set of [[Data link|link]]s to other nodes (its ''neighbors'' or [[routing table]]). Together, these links form the overlay network.<ref>((Citation|last1=Galuba|first1=Wojciech|title=Peer to Peer Overlay Networks: Structure, Routing and Maintenance|date=2009|encyclopedia=Encyclopedia of Database Systems|pages=2056–2061|editor-last=LIU|editor-first=LING|editor-link=Ling Liu (computer scientist)|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_1215|isbn=9780387399409|last2=Girdzijauskas|first2=Sarunas|editor2-last=ÖZSU|editor2-first=M. TAMER))</ref> A node picks its neighbors according to a certain structure, called the [[network topology|network's topology]].

All DHT topologies share some variant of the most essential property: for any key ((mvar|k)), each node either has a node ID that owns ((mvar|k)) or has a link to a node whose node ID is ''closer'' to ((mvar|k)), in terms of the keyspace distance defined above. It is then easy to route a message to the owner of any key ((mvar|k)) using the following [[greedy algorithm]] (that is not necessarily globally optimal): at each step, forward the message to the neighbor whose ID is closest to ((mvar|k)). When there is no such neighbor, then we must have arrived at the closest node, which is the owner of ((mvar|k)) as defined above. This style of routing is sometimes called [[key-based routing]].

Beyond basic routing correctness, two important constraints on the topology are to guarantee that the maximum number of [[Hop (networking)|hops]] in any route (route length) is low, so that requests complete quickly; and that the maximum number of neighbors of any node (maximum node [[Degree (graph theory)|degree]]) is low, so that maintenance overhead is not excessive. Of course, having shorter routes requires higher [[maximum degree]]. Some common choices for maximum degree and route length are as follows, where ((mvar|n)) is the number of nodes in the DHT, using [[Big O notation]]:

{| class="wikitable"
|-
! Max. degree !! Max route length !! Used in !! Note
|-
| <math>O(1)</math> || <math>O(n)</math> ||  || Worst lookup lengths, with likely much slower lookups times
|-
| <math>O(1)</math> || <math>O(\log n)</math> || [[Koorde]] (with constant degree) || More complex to implement, but acceptable lookup time can be found with a fixed number of connections
|-
| <math>O(\log n)</math> || <math>O(\log n)</math> || [[Chord (peer-to-peer)|Chord]] <br/> [[Kademlia]] <br/> [[Pastry (DHT)|Pastry]] <br/> [[Tapestry (DHT)|Tapestry]] || Most common, but not optimal (degree/route length).  Chord is the most basic version, with Kademlia seeming the most popular optimized variant (should have improved average lookup)
|-
| <math>O(\log n)</math> || <math>O(\log n/\log (\log n))</math> || [[Koorde]] (with optimal lookup) || More complex to implement, but lookups might be faster (have a lower worst case bound)
|-
| <math>O(\sqrt{n})</math> || <math>O(1)</math> ||  || Worst local storage needs, with much communication after any node connects or disconnects
|}

The most common choice, <math>O(\log n)</math> degree/route length, is not optimal in terms of degree/route length tradeoff, but such topologies typically allow more flexibility in choice of neighbors. Many DHTs use that flexibility to pick neighbors that are close in terms of latency in the physical underlying network. In general, all DHTs construct navigable small-world network topologies, which trade-off route length vs. network degree.<ref>((Cite book|url=https://infoscience.epfl.ch/record/130838?ln=en|title=Designing peer-to-peer overlays a small-world perspective|last=Girdzijauskas|first=Sarunas|date=2009|website=epfl.ch|publisher=EPFL))</ref>

Maximum route length is closely related to [[Diameter (graph theory)|diameter]]: the maximum number of hops in any shortest path between nodes. Clearly, the network's worst case route length is at least as large as its diameter, so DHTs are limited by the degree/diameter tradeoff<ref>((citation |url=http://maite71.upc.es/grup_de_grafs/table_g.html |title=The (Degree, Diameter) Problem for Graphs |publisher=Maite71.upc.es |access-date=2012-01-10 |archive-url=https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/ |archive-date=2012-02-17 |url-status=dead ))</ref> that is fundamental in [[graph theory]]. Route length can be greater than diameter, since the greedy routing algorithm may not find shortest paths.<ref>Gurmeet Singh Manku, Moni Naor, and Udi Wieder. [http://citeseer.ist.psu.edu/naor04know.html "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks"]. Proc. STOC, 2004.</ref>

=== Algorithms for overlay networks ===
Aside from routing, there exist many algorithms that exploit the structure of the overlay network for sending a message to all nodes, or a subset of nodes, in a DHT.<ref>((cite web|author=[[Ali Ghodsi]]|url=http://www.sics.se/~ali/thesis/|title= Distributed k-ary System: Algorithms for Distributed Hash Tables |archive-url=https://web.archive.org/web/20070522060750/http://www.sics.se/~ali/thesis/ |archive-date=22 May 2007|date=22 May 2007 |url-status=dead)). KTH-Royal Institute of Technology, 2006.</ref> These algorithms are used by applications to do [[overlay multicast]], range queries, or to collect statistics. Two systems that are based on this approach are Structella,<ref>((cite journal |last1=Castro |first1=Miguel |last2=Costa |first2=Manuel |last3=Rowstron |first3=Antony |title=Should we build Gnutella on a structured overlay? |journal=ACM SIGCOMM Computer Communication Review |date=1 January 2004 |volume=34 |issue=1 |pages=131 |doi=10.1145/972374.972397 |citeseerx=10.1.1.221.7892 |s2cid=6587291 |url=http://nms.lcs.mit.edu/HotNets-II/papers/structella.pdf ))</ref> which implements flooding and random walks on a Pastry overlay, and DQ-DHT, which implements a dynamic querying search algorithm over a Chord network.<ref>((cite journal |last1=Talia |first1=Domenico |last2=Trunfio |first2=Paolo |title=Enabling Dynamic Querying over Distributed Hash Tables |journal=Journal of Parallel and Distributed Computing |date=December 2010 |volume=70 |issue=12 |pages=1254–1265 |doi=10.1016/j.jpdc.2010.08.012 ))</ref>

== Security ==

Because of the decentralization, fault tolerance, and scalability of DHTs, they are inherently more resilient against a hostile attacker than a centralized system.((Vague|date=June 2016))

Open systems for [[distributed data storage]] that are robust against massive hostile attackers are feasible.<ref>
Baruch Awerbuch, Christian Scheideler.
"Towards a scalable and robust DHT".
2006.
((doi|10.1145/1148109.1148163))
</ref>

A DHT system that is carefully designed to have [[Byzantine fault tolerance]] can defend against a security weakness, known as the [[Sybil attack]], which affects most current DHT designs.<ref>
Maxwell Young; Aniket Kate; Ian Goldberg; Martin Karsten.
[http://www.cypherpunks.ca/~iang/pubs/robustMessagePassing.pdf "Practical Robust Communication in DHTs Tolerating a Byzantine Adversary"].
</ref><ref>
Natalya Fedotova; Giordano Orzetti; Luca Veltri; Alessandro Zaccagnini.
"Byzantine agreement for reputation management in DHT-based peer-to-peer networks".
((doi|10.1109/ICTEL.2008.4652638))
</ref> Whanau is a DHT designed to be resistant to Sybil attacks.<ref>
Whanau: A Sybil-proof Distributed Hash Table
https://pdos.csail.mit.edu/papers/whanau-nsdi10.pdf
</ref>

Petar Maymounkov, one of the original authors of [[Kademlia]], has proposed a way to circumvent the weakness to the Sybil attack by incorporating social trust relationships into the system design.<ref>((cite journal |author=Chris Lesniewski-Laas |title=A Sybil-proof one-hop DHT |pages=20 |url=http://pdos.csail.mit.edu/papers/sybil-dht-socialnets08.pdf ))</ref> The new system, codenamed Tonika or also known by its domain name as 5ttt, is based on an algorithm design known as "electric routing" and co-authored with the mathematician Jonathan Kelner.<ref>((cite journal |author=Jonathan Kelner, Petar Maymounkov |title=Electric routing and concurrent flow cutting |url=https://archive.org/details/arxiv-0909.2859 |arxiv=0909.2859|bibcode=2009arXiv0909.2859K|year=2009 ))</ref> Maymounkov has now undertaken a comprehensive implementation effort of this new system. However, research into effective defences against Sybil attacks is generally considered an open question, and wide variety of potential defences are proposed every year in top security research conferences.((Citation needed|date=May 2020))

== Implementations ==
Most notable differences encountered in practical instances of DHT implementations include at least the following:
* The address space is a parameter of DHT. Several real-world DHTs use 128-bit or 160-bit key space.
* Some real-world DHTs use hash functions other than [[SHA-1]].
* In the real world the key ((var serif|1=k)) could be a hash of a file's ''content'' rather than a hash of a file's ''name'' to provide [[content-addressable storage]], so that renaming of the file does not prevent users from finding it.
* Some DHTs may also publish objects of different types. For example, key ((var serif|1=k)) could be the node ((var serif|1=ID)) and associated data could describe how to contact this node. This allows publication-of-presence information and often used in IM applications, etc. In the simplest case, ((var serif|1=ID)) is just a random number that is directly used as key ((var serif|1=k)) (so in a 160-bit DHT ((var serif|1=ID)) will be a 160-bit number, usually randomly chosen). In some DHTs, publishing of nodes' IDs is also used to optimize DHT operations.
* Redundancy can be added to improve reliability.  The ((var serif|1=(k, data))) key pair can be stored in more than one node corresponding to the key. Usually, rather than selecting just one node, real world DHT algorithms select ((var serif|1=i)) suitable nodes, with ((var serif|1=i)) being an implementation-specific parameter of the DHT. In some DHT designs, nodes agree to handle a certain keyspace range, the size of which may be chosen dynamically, rather than hard-coded.
* Some advanced DHTs like [[Kademlia]] perform iterative lookups through the DHT first in order to select a set of suitable nodes and send ((var serif|1=put(k, data))) messages only to those nodes, thus drastically reducing useless traffic, since published messages are only sent to nodes that seem suitable for storing the key ((var serif|1=k)); and iterative lookups cover just a small set of nodes rather than the entire DHT, reducing useless forwarding. In such DHTs, forwarding of ((Var serif|put(k, data))) messages may only occur as part of a self-healing algorithm: if a target node receives a ((var serif|1=put(k, data))) message, but believes that ((var serif|1=k)) is out of its handled range and a closer node (in terms of DHT keyspace) is known, the message is forwarded to that node. Otherwise, data are indexed locally. This leads to a somewhat self-balancing DHT behavior. Of course, such an algorithm requires nodes to publish their presence data in the DHT so the iterative lookups can be performed.
* Since on most machines sending messages is much more expensive than local hash table accesses, it makes sense to bundle many messages concerning a particular node into a single batch. Assuming each node has a local batch consisting of at most ((var serif|1=b)) operations, the bundling procedure is as follows. Each node first sorts its local batch by the identifier of the node responsible for the operation. Using [[bucket sort]], this can be done in ((var serif|1=O(b + n))), where ((var serif|1=n)) is the number of nodes in the DHT. When there are multiple operations addressing the same key within one batch, the batch is condensed before being sent out. For example, multiple lookups of the same key can be reduced to one or multiple increments can be reduced to a single add operation. This reduction can be implemented with the help of a temporary local hash table. Finally, the operations are sent to the respective nodes.<ref>((Cite book|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox|last1=Sanders|first1=Peter|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3|language=en))</ref>

== Examples ==

=== DHT protocols and implementations ===
* [[Apache Cassandra]]
* [[BATON Overlay]]
* [[Mainline DHT]] – standard DHT used by BitTorrent (based on [[Kademlia]] as provided by Khashmir)<ref>[http://www.tribler.org/trac/wiki/Khashmir Tribler wiki] ((webarchive |url=https://web.archive.org/web/20101204111423/http://www.tribler.org/trac/wiki/Khashmir |date=December 4, 2010 )) retrieved January 2010.</ref>
*[[Content addressable network]] (CAN)
* [[Chord (DHT)|Chord]]
* [[Koorde]]
* [[Kademlia]]
* [[Pastry (DHT)|Pastry]]
* [[P-Grid]]
* [[Riak]]
* [[Tapestry (DHT)|Tapestry]]
* [[TomP2P]]
* [[Voldemort (distributed data store)|Voldemort]]

=== Applications using DHTs ===
<!-- NOTE ABOUT ADDING ITEMS TO THIS SECTION: Please provide a reference so the editors know that (1) the application actually uses a DHT, and (2) the project is notable as opposed to just someone's project from networking class. You can do this by providing a wikilink here or putting a note or external link on the Talk page. PLEASE DO NOT ADD BITTORRENT CLIENTS as these are already covered via the link to "Comparison of BitTorrent clients"; there's no reason to duplicate that list here. -->
* [[BTDigg]]: BitTorrent DHT search engine
* [[Codeen]]: web caching
* [[Freenet]]: a censorship-resistant anonymous network
* [[GlusterFS]]: a distributed file system used for storage virtualization
* [[GNUnet]]: Freenet-like distribution network including a DHT implementation
* [[I2P]]: An open-source anonymous peer-to-peer network
* [[I2P | I2P-Bote]]: serverless secure anonymous email
* [[InterPlanetary File System|IPFS]]: A content-addressable, peer-to-peer hypermedia distribution protocol
* [[JXTA]]: open-source P2P platform
* [[LBRY]]: A blockchain-based content sharing protocol which uses a [[Kademlia]]-influenced DHT system for content distribution
* [[Oracle Coherence]]: an in-memory data grid built on top of a Java DHT implementation
* [[Perfect Dark (P2P)|Perfect Dark]]: a [[peer-to-peer]] [[file-sharing]] application from Japan
* [[Retroshare]]: a [[Friend-to-friend]] network<ref>[http://retroshare.sourceforge.net/wiki/index.php/Frequently_Asked_Questions#4-1_How_does_RetroShare_know_my_friend.27s_IP_address_and_port.3F_Why_don.27t_I_need_a_static_IP_address.3F_What_is_DHT_for.3F Retroshare FAQ] ((Webarchive|url=https://web.archive.org/web/20130717094704/http://retroshare.sourceforge.net/wiki/index.php/Frequently_Asked_Questions#4-1_How_does_RetroShare_know_my_friend.27s_IP_address_and_port.3F_Why_don.27t_I_need_a_static_IP_address.3F_What_is_DHT_for.3F |date=2013-07-17 )) retrieved December 2011</ref>
* [[Jami (software)|Jami]]: a privacy-preserving voice, video and chat communication platform, based on a Kademlia-like DHT
* [[Tox (protocol)|Tox]]: an [[instant messaging]] system intended to function as a [[Skype]] replacement
* [[Twister (software)|Twister]]: a [[microblogging]] [[peer-to-peer]] platform
* [[YaCy]]: a distributed [[Web search engine|search engine]]

== See also ==

* [[Couchbase Server]]: a persistent, replicated, clustered distributed object storage system compatible with memcached protocol.
* [[Memcached]]: a high-performance, distributed memory object caching system.
* [[Prefix hash tree]]: sophisticated querying over DHTs.
* [[Merkle tree]]: tree having every non-leaf node labelled with the hash of the labels of its children nodes.
* Most [[distributed data store]]s employ some form of DHT for lookup.
* [[Skip graph]]s are an efficient data structure for implementing DHTs.

== References ==
((Reflist|30em))

== External links ==
* [http://linuxjournal.com/article/6797 Distributed Hash Tables, Part 1] by Brandon Wiley.
* [http://ast-deim.urv.cat/cpairot/dhts.html Distributed Hash Tables links] Carles Pairot's Page on DHT and P2P research
* [https://web.archive.org/web/*/http://kademlia.scs.cs.nyu.edu/ kademlia.scs.cs.nyu.edu] Archive.org snapshots of kademlia.scs.cs.nyu.edu
* ((cite CiteSeerX | citeseerx = 10.1.1.111.4197 | title = IEEE Survey on overlay network schemes | author1 = Eng-Keong Lua | first2 = Jon | last2 = Crowcroft | first3 = Marcelo | last3 = Pias | first4 = Ravi | last4 = Sharma | first5 = Steve | last5 = Lim | postscript = : | year = 2005 )) covering unstructured and structured decentralized overlay networks including DHTs (Chord, Pastry, Tapestry and others).
* [http://www.cs.helsinki.fi/u/jakangas/MLDHT/ Mainline DHT Measurement] at Department of Computer Science, University of Helsinki, Finland.

((BitTorrent))

((DEFAULTSORT:Distributed Hash Table))
[[Category:Distributed data storage]]
[[Category:File sharing]]
[[Category:Distributed data structures]]
[[Category:Hash-based data structures]]
[[Category:Network architecture]]
[[Category:Hashing]]

Pages transcluded onto the current version of this page (help):

Distributed hash table (edit)
Template:( (view source) (protected)
Template:) (view source) (protected)
Template:Ambox (view source) (template editor protected)
Template:BitTorrent (edit)
Template:Catalog lookup link (view source) (template editor protected)
Template:Category handler (view source) (protected)
Template:Citation (view source) (protected)
Template:Citation needed (view source) (protected)
Template:Cite CiteSeerX (view source) (semi-protected)
Template:Cite book (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cite news (view source) (protected)
Template:Cite web (view source) (protected)
Template:Delink (view source) (protected)
Template:Doi (view source) (template editor protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Fix (view source) (protected)
Template:Fix-span (view source) (template editor protected)
Template:Fix/category (view source) (protected)
Template:Further (view source) (template editor protected)
Template:Hlist/styles.css (view source) (protected)
Template:Icon (view source) (template editor protected)
Template:Ifsubst (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Math (view source) (template editor protected)
Template:More citations needed (view source) (template editor protected)
Template:Mset (view source) (semi-protected)
Template:Mvar (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Pagetype (view source) (protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Template:Spaced en dash (view source) (template editor protected)
Template:Spaced ndash (view source) (template editor protected)
Template:Vague (view source) (extended confirmed protected)
Template:Var serif (edit)
Template:Var serif/styles.css (edit)
Template:Webarchive (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Catalog lookup link (view source) (template editor protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:DecodeEncode (view source) (template editor protected)
Module:Delink (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:GetParameters (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Icon (view source) (template editor protected)
Module:Icon/data (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:String2 (view source) (template editor protected)
Module:Unsubst (view source) (protected)
Module:Webarchive (view source) (template editor protected)
Module:Webarchive/data (view source) (template editor protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Distributed hash table.

Retrieved from "https://en.wikipedia.org/wiki/Distributed_hash_table"