Verteilte Hashtabelle

Eine verteilte Hashtabelle ({{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}, DHT) ist eine Datenstruktur, die beispielsweise verwendet wird, um den Speicherplatz einer Datei in einem P2P-System effizient zu verteilen.

Die Daten werden möglichst gleichmäßig über die vorhandenen Speicherknoten verteilt. Jeder Speicherknoten entspricht dabei einem Eintrag in der Hashtabelle. Die selbstorganisierende Datenstruktur kann den Ausfall, Beitritt und Austritt von Knoten abbilden. Die Grundlage für verteilte Hashtabellen bilden konsistente Hash-Funktionen.

Man unterscheidet DHTs nach dem Speicherschema. Die Daten können direkt innerhalb der DHT abgelegt werden (direct storage) oder in der DHT kann ein Verweis auf die Daten vorgehalten werden (indirect storage). Direct Storage bietet sich nur für kleine Daten (< 1 kB) an, da sonst das System zu unflexibel werden würde.

Eigenschaften

Eigenschaften von DHTs sind:

Fehlertoleranz: Das System sollte zuverlässig funktionieren, auch wenn Knoten ausfallen oder das System verlassen.
Lastenverteilung: Schlüssel werden gleichmäßig auf alle Knoten verteilt.
Robustheit: Das System sollte „korrekt“ funktionieren können, auch wenn ein Teil (möglicherweise ein Großteil) der Knoten versucht, das System zu stören.
Selbstorganisation: Es ist keine manuelle Konfiguration nötig.
Skalierbarkeit: Das System sollte in der Lage sein, auch mit einer großen Anzahl von Knoten funktionsfähig zu bleiben.

Prinzipielle Arbeitsweise

Mittels einer Hashfunktion werden den Datenobjekten Schlüssel in einem linearen Wertebereich vergeben, welcher möglichst gleichmäßig über die Knoten der Knotenmenge verteilt wird. Für jeden Teilbereich des Schlüsselraumes ist dabei mindestens ein Knoten zuständig. Oft sind jedoch auch mehrere Knoten für denselben Bereich verantwortlich, wobei sich die Zuständigkeiten dynamisch ändern. Ein Beitrittsprotokoll regelt die Aufnahme neuer Knoten in das existierende System. Das Protokoll stellt dann die Verbindungen zu den Nachbarknoten her und regelt üblicherweise auch die Konstruktion von Routingtabellen.

Die Routingtabellen werden von den DHT-Knoten zur Ermittlung anderer Knoten benutzt, die für bestimmte Datensätze zuständig sind. Die Definition der „Entfernung“ ist dabei mit der Struktur und der Topologie verbunden und variiert in unterschiedlichen Systemen. Sie muss nicht zwingend mit der physischen Organisation der Knoten übereinstimmen. Eine verteilte Hashtabelle, die ihre Knoten in einem euklidischen Raum platziert, könnte den Knoten mit dem geringsten euklidischen Abstand zu einem Schlüssel wählen. Die Routingtabellen sollen es jedem Knoten erlauben, den nächsten Knoten zu einem Schlüssel in O(log n) Suchschritten zu erreichen.

Durch eine generische Schnittstelle, die nur zwei Funktionen publish(Schlüssel, Inhalt) und lookup(Schlüssel) anbietet, lassen sich die implementierten Algorithmen auswechseln.

Partitionierung des Schlüsselraums

Bei den meisten DHTs geschieht die Abbildung von Schlüsseln auf Knoten mittels einer Variante von konsistentem Hashing oder Rendezvouz-Hashing. Diese beiden Varianten wurden wohl gleichzeitig, aber unabhängig entwickelt, um das DHT-Problem zu lösen.

Sowohl konsistentes Hashing als auch Rendezvouz-Hashing haben die grundlegende Eigenschaft, dass sich bei Beitritt oder Austritt eines Knotens nur die Schlüssel der benachbarten Knoten ändern und alle anderen Knoten nicht beeinträchtigt werden. In konventionellen Hashtabellen hingegen wird bei hinzufügen oder entfernen eines Buckets fast der vollständige Schlüsselbereich neu verteilt. Wenn sich die Zuständigkeit von Datenobjekten ändert, ist eine Daten-Umverteilung notwendig. Diese belastet das Netzwerk und die Datenbandbreite. Deshalb werden DHTs so gestaltet, dass sie auch häufige Ein- und Austritte von Knoten effizient unterstützen können.

Konsistentes Hashing

Beim konsistenten Hashing wird eine Distanzfunktion <math>\delta(k_1, k_2)</math> verwendet. Diese gibt die Distanz zwischen zwei Schlüsseln <math>k_1</math> und <math>k_2</math> an. Die Distanz ist dabei unabhängig von der geographischen Distanz oder der Latenz im Netzwerk. Außerdem erhält jeder Knoten <math>x</math> des Netzwerks einen Schlüssel, welchen wir seinen Identifikator <math>i_x</math> (ID von Knoten <math>x</math>) nennen. Jeder Knoten ist dann für die Speicherung derer Elemente zuständig, deren Distanz zu seiner ID am geringsten ist: <math>x = \operatorname{argmin}_y \delta(k, i_y)</math>.

Beispielsweise setzt Chord konsistentes Hashing ein, wobei die Knoten als Punkte auf einem Kreis und <math>\delta (k_{1},k_{2})</math> als der Kreisbogen von <math>k_1</math> nach <math>k_2</math> im Uhrzeigersinn aufgefasst werden. Der kreisförmige Schlüsselraum besteht also aus zusammenhängenden Segmenten, deren Endpunkte die Knoten-IDs sind. Wenn also zum Beispiel <math>i_1</math> und <math>i_2</math> zwei im Kreis aufeinander folgende Knoten-IDs sind, dann ist der Knoten <math>i_1</math> für alle Schlüssel zwischen <math>i_1</math> und <math>i_2</math> zuständig.

Rendezvous-Hashing

Beim Rendezvouz-Hashing benutzen alle Clients, welche einen Schlüssel auf einen der <math>n</math> Knoten abbilden wollen, die gleiche, zu Beginn gewählte Hashfunktion <math>h()</math>. Außerdem haben alle Clients die gleiche Liste von IDs <math>\{S_1, S_2, ..., S_n \}</math>, eine für jeden Knoten. Um den richtigen Knoten für einen Schlüssel <math>k</math> zu bestimmen, werden zunächst <math>n</math> Hash-Gewichte <math>w_1 = h(S_1, k),\ w_2 = h(S_2, k),\ ...,\ w_n = h(S_n, k)</math> berechnet. Der Schlüssel wird dann mit dem dem Maximum dieser Werte entsprechenden Knoten assoziiert. Ein Knoten mit ID <math>S_x</math> ist also für alle Schlüssel <math>k_m</math> zuständig, deren Hash-Gewicht <math>h(S_x, k_m)</math> höher als die Hash-Gewichte aller anderen Knoten für den Schlüssel ist.

Lokalitätserhaltendes Hashing

Lokalitätserhaltendes Hashing stellt sicher, dass ähnliche Schlüssel auch ähnlichen Knoten zugeteilt werden. Dadurch können effizientere Range Queries ermöglicht werden. Dabei kann es allerdings vorkommen, dass die Verteilung des Schlüsselraums auf die Knoten und damit deren Auslastung nicht mehr uniform zufällig ist. Das Framework Self-Chord zum Beispiel macht Objektschlüssel von Knoten-IDs unabhängig und sortiert Schlüssel entlang eines Ringspeichers mit Hilfe eines statistischen Ansatzes, der auf dem Schwarmintelligenz-Paradigma beruht.<ref>{{#invoke:Vorlage:Literatur|f}}{{#if:

       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: IEEE/ACM Transactions on Networking
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:Forestiero|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref> Das Sortieren stellt sicher, dass benachbarte Knoten für ähnliche Schlüssel zuständig sind und Abfragen wie z. B. Range Queries so in logarithmischer Zeit ausgeführt werden können.

Overlay-Netz

Das Overlay-Netz verbindet die Knoten, sodass diese den jeweiligen zuständigen Knoten für Schlüssel finden können. Dabei hält jeder Knoten in einer Routingtabelle Verbindungen zu anderen Knoten (seinen Nachbarn). Ein Knoten wählt seine Nachbarn entsprechend der Netzwerktopologie (Struktur des Netzwerks).

Alle DHT-Topologien verbindet eine grundlegende Eigenschaft: für jeden Schlüssel <math>k</math> weiß jeder Knoten entweder die ID des Knotens, der für <math>k</math> zuständig ist, oder er hat einen Link zu einem Knoten, dessen ID näher an <math>k</math> ist, definiert durch ein Distanzmaß in Abschnitt Partitionierung des Schlüsselraums. Eine Nachricht kann dann einfach an den zuständigen Knoten von <math>k</math> geroutet werden: Bei jedem Schritt wird die Nachricht an denjenigen Knoten weitergeleitet, dessen ID <math>k</math> am nächsten ist, bis der zuständige Knoten erreicht wird. Dieser Algorithmus ist im Allgemeinen nicht global optimal. Manchmal wird dieses Verfahren Schlüssel-basiertes Routing genannt.

Das Overlay-Netz hat zwei Parameter, welche einen großen Einfluss auf seine Leistung haben. Die maximale Routenlänge sollte klein sein, damit Pakete schnell ankommen, und der maximale Knotengrad sollte klein sein, damit der Overhead pro besuchtem Knoten klein ist. Dabei stehen die beiden Parameter in einem Tradeoff-Verhältnis. Einige typische Verhältnisse sind in der folgenden Tabelle beschrieben.

Max. Knotengrad	Max. Routenlänge	Benutzt in	Bemerkung
<math>O(1)</math>	<math>O(n)</math>		Schlechtestmögliche Routenlänge, Anfragen werden sehr langsam
<math>O(\log n)</math>	<math>O(\log n)</math>	Chord Kademlia Pastry Tapestry	Am verbreitetsten aber nicht optimal (Nachbargrad/Routenlänge-Verhältnis). Chord ist die einfachste Version, Kademlia scheint die beliebteste optimierte Variante zu sein (sollte verbesserte durschn. Zeit für Anfragen haben)
<math>O(\log n)</math>	<math>O(\log n/\log (\log n))</math>	Koorde	Wohl komplexere Implementierung aber Anfragen können schneller sein (niedrigere Worst-Case-Schranke)
<math>O(\sqrt{n})</math>	<math>O(1)</math>		Höchste lokale Speicherplatzanforderungen, hohe Kommunikationslast nach Beitritt und Austritt eines Knotens

<math>O(\log n)</math> als maximaler Nachbargrad und maximale Routenlänge ist die am weitesten verbreitete Parametrisierung. Obwohl der Nachbargrad/Routenlänge-Tradeoff bei ihr nicht optimal ist, ermöglicht sie oft eine höhere Flexibilität bei der Wahl der Nachbarn. Viele DHTs nutzen diese Flexibilität, um Nachbarn mit möglichst geringer Latenz im darunterliegenden physikalischen Netzwerk auszuwählen. Im Allgemeinen erstellen DHTs navigierbare kleine-Welt-Netzwerk-Topologien mit dem Tradeoff zwischen Routenlänge und Netzwerkgrad<ref>{{#invoke:Vorlage:Literatur|f}}{{#if: | {{#if: Vorlage:Cite book/ParamBool | Vorlage:Toter Link/archivebot | Vorlage:Webarchiv/archiv-bot }}

  }}{{#invoke:TemplatePar|check

|all = title= |opt = vauthors= author= author-link= authorlink= author1= author-link1= author1-link= first= last= first1= last1= first2= last2= author2= first3= last3= author3= first4= last4= author4= first5= last5= author5= first6= last6= author6= first7= last7= author7= first8= last8= author8= others= coauthors= script-title= trans-title= orig-date= orig-year= chapter= chapter-url= editor= editor-first= editor-last= editor-first1= editor-last1= editor-first2= editor-last2= editor-first3= editor-last3= editor-link= editor-link1= language= format= others= series= issue= number= edition= volume= publisher= location= date= year= isbn= page= at= pages= arxiv= doi= jstor= bibcode= pmc= pmid= lccn= oclc= id= url= url-status= access-date= accessdate= archive-url= archiveurl= archive-date= archivedate= quote= url-access= ref= coauthors= origyear= archivebot= offline= |cat = Wikipedia:Vorlagenfehler/Vorlage:Cite book |errNS = 0 |template = Vorlage:Cite book |format = @@@ |preview = 1

  }}Vorlage:Cite book/URLVorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if: Vorlage:Cite book/ParamBool

| Vorlage:Cite book/Meldung

  }}{{#if:  Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:Sarunas Girdzijauskas|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>.

Die maximale Routenlänge ist eng verwandt mit dem Durchmesser (des Netzwerks): der maximalen Anzahl Hops in einem beliebigen kürzesten Pfad zwischen zwei Knoten. Die Worst-Case-Routenlänge des Netzwerks ist offensichtlich mindestens so groß wie der Durchmesser, folglich haben DHTs die in der Graphentheorie fundamentale Limitierung des Knotengrad/Durchmesser-Tradeoffs<ref>{{#if:Vorlage:Cite book/URL|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:{{#if:

               |  
               | {{#if: 
                 | {{#if: 
                     |  [[|Vorlage:Cite book/Name]]
                     | Vorlage:Cite book/Name
                   }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                        }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}
             }}Vorlage:Cite book/Name|{{#if: 
               |  
               | {{#if: 
                 | {{#if: 
                     |  [[|Vorlage:Cite book/Name]]
                     | Vorlage:Cite book/Name
                   }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                        }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if: 
                     | {{#if:  
                         | , [[|Vorlage:Cite book/Name]]
                         | Vorlage:Cite book/Name
                       }}
                 }}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}{{#if:|Vorlage:Cite book/Name}}
             }}Vorlage:Cite book/Name: }}{{#if:Vorlage:Cite book/URL|{{#if:{{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1=Vorlage:Cite book/URL}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}}}]{{#if:| ()}}{{#if:{{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}| {{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}}}}}}}|{{#if:http://maite71.upc.es/grup_de_grafs/table_g.html%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7CVorlage:Cite book/URL}}|{{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1={{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}}}}}|[{{#invoke:URLutil|getNormalized|1=http://maite71.upc.es/grup_de_grafs/table_g.html}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1={{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}}}}}]}}{{#if:| ({{#if:{{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}Vorlage:Cite book/URLMaite71.upc.es {{#if:  | via {{{via}}} }}Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}||1}}}}
          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}{{#if:  | {{{at}}}{{#if:  | ,  }}}}{{#if:  | {{{id}}}{{#if:  | ,  }}}}{{#if:  | {{{doi}}}{{#if:  | ,  }}}}{{#if:  | PMID {{{pmid}}}{{#if:  | ,  }}}}{{#if:  | {{{arxiv}}}{{#if:  | ,  }}}}{{#if:  | Bibcode: {{{bibcode}}}{{#if:  | ,  }}}}{{#if:  | Volltext bei PMC: {{{pmc}}}{{#if:  | ,  }}}}| ; 
              | )}}}}}}{{#if:{{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}| {{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}}}}}}}}}{{#if:http://maite71.upc.es/grup_de_grafs/table_g.html%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://maite71.upc.es/grup_de_grafs/table_g.html}}%7C%7C URL ungültig}}}}{{#if:{{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}|{{#if:{{#invoke:WLink|isValidLinktext|1={{#if: The (Degree,Diameter) Problem for Graphs | {{#invoke: WLink|getEscapedTitle|1=The (Degree,Diameter) Problem for Graphs}} | ? }}|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=}}}}{{#if: Maite71.upc.es {{#if:  | via {{{via}}} }}| Maite71.upc.es {{#if:  | via {{{via}}} }}{{#if: Vorlage:Cite book/DateVorlage:Cite book/URL|,|{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}|;|,}}}}}}}}{{#if: Vorlage:Cite book/Date| {{#if:{{#invoke:DateTime|format|Vorlage:Cite book/Date|noerror=1}}
            |{{#invoke:DateTime|format|Vorlage:Cite book/Date|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=Vorlage:Cite book/Date|class=Zitationswartung}} }}{{#if: Vorlage:Cite book/URL|,|{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}|;|,}}}}}}}}{{#if: | S. {{#if: Vorlage:Cite book/URL|,|{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}|;|,}}}}}}}}{{#if: Vorlage:Cite book/URL{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}| {{#if:Vorlage:Cite book/DateMaite71.upc.es {{#if:  | via {{{via}}} }}|{{#if:Vorlage:Cite book/URL|archiviert|ehemals}}|{{#if:Vorlage:Cite book/URL|Archiviert|Ehemals}}}} {{#if:Vorlage:Cite book/URL|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}| (nicht mehr online verfügbar)}}{{#if: Vorlage:Cite book/URL| am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|Vorlage:Cite book/URL{{#if:321340||(?)}}}}}}{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }}|;}}}}{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }}| {{#if:Vorlage:Cite book/DateMaite71.upc.es {{#if:  | via {{{via}}} }}Vorlage:Cite book/URL{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf={{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }}|class=Zitationswartung}} }} {{#invoke:DateTime|format|{{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }}|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}{{#if:  | {{{at}}}{{#if:  | ,  }}}}{{#if:  | {{{id}}}{{#if:  | ,  }}}}{{#if:  | {{{doi}}}{{#if:  | ,  }}}}{{#if:  | PMID {{{pmid}}}{{#if:  | ,  }}}}{{#if:  | {{{arxiv}}}{{#if:  | ,  }}}}{{#if:  | Bibcode: {{{bibcode}}}{{#if:  | ,  }}}}{{#if:  | Volltext bei PMC: {{{pmc}}}{{#if:  | ,  }}}}|{{#if:{{#if:  | ( }}{{#if:  | Originaltitel: {{{script-title}}} }}{{#if:   | {{#if:  | ,  }}deutsch: {{{trans-title}}} }}{{#if:  | ) }}Vorlage:Cite book/URLMaite71.upc.es {{#if:  | via {{{via}}} }}Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: {{#if:  | {{{at}}}{{#if:  | ,  }}}}{{#if:  | {{{id}}}{{#if:  | ,  }}}}{{#if:  | {{{doi}}}{{#if:  | ,  }}}}{{#if:  | PMID {{{pmid}}}{{#if:  | ,  }}}}{{#if:  | {{{arxiv}}}{{#if:  | ,  }}}}{{#if:  | Bibcode: {{{bibcode}}}{{#if:  | ,  }}}}{{#if:  | Volltext bei PMC: {{{pmc}}}{{#if:  | ,  }}}}|{{#ifeq:{{#if:en|en|de}}|de||, }}{{#if:  | {{{at}}}{{#if:  | ,  }}}}{{#if:  | {{{id}}}{{#if:  | ,  }}}}{{#if:  | {{{doi}}}{{#if:  | ,  }}}}{{#if:  | PMID {{{pmid}}}{{#if:  | ,  }}}}{{#if:  | {{{arxiv}}}{{#if:  | ,  }}}}{{#if:  | Bibcode: {{{bibcode}}}{{#if:  | ,  }}}}{{#if:  | Volltext bei PMC: {{{pmc}}}{{#if:  | ,  }}}}}})}}{{#if: Vorlage:Cite book/DateVorlage:Cite book/URL{{#if: {{#if: 2012-01-10
                 | {{#iferror: {{#invoke:DateTime|format|2012-01-10|ISO}}
                     | 0001-01-01
                   }}
                 | 0001-01-01
               }} | {{#if:{{#invoke:TemplUtl|faculty|{{#if: 2012-01-10
                         | {{#if: {{#invoke:DateTime|format|2012-01-10 |ISO|noerror=1}} || 1 }}
                         | 1
                       }}}}||1}} }}en{{#if:  | {{{at}}}{{#if:  | ,  }}}}{{#if:  | {{{id}}}{{#if:  | ,  }}}}{{#if:  | {{{doi}}}{{#if:  | ,  }}}}{{#if:  | PMID {{{pmid}}}{{#if:  | ,  }}}}{{#if:  | {{{arxiv}}}{{#if:  | ,  }}}}{{#if:  | Bibcode: {{{bibcode}}}{{#if:  | ,  }}}}{{#if:  | Volltext bei PMC: {{{pmc}}}{{#if:  | ,  }}}}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if:

   | {{#if: 
       | {{#if: 
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|Vorlage:Cite book/URL}}|{{#if:Vorlage:Cite book/URL||{{#ifeq: Vorlage:Cite book/URL | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
      | {{#if:{{#invoke:URLutil|isWebURL|http://maite71.upc.es/grup_de_grafs/table_g.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://maite71.upc.es/grup_de_grafs/table_g.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
       | {{#if:{{#invoke:URLutil|isWebURL|http://maite71.upc.es/grup_de_grafs/table_g.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[http://maite71.upc.es/grup_de_grafs/table_g.html }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
      | {{#if:{{#invoke:URLutil|isWebURL|http://maite71.upc.es/grup_de_grafs/table_g.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://maite71.upc.es/grup_de_grafs/table_g.html Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: http://maite71.upc.es/grup_de_grafs/table_g.html
       | {{#if:{{#invoke:URLutil|isWebURL|http://maite71.upc.es/grup_de_grafs/table_g.html}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[http://maite71.upc.es/grup_de_grafs/table_g.html }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp=|text={{#if:Vorlage:Cite book/URL|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}{{#invoke:TemplatePar|check

   |all     = url= title=
   |opt     =  script-title= trans-title= archive-url= archiveurl= archive-date= archivedate= authors= vauthors= author= author1= authorlink= authorlink1= author-link= author-link1= author2= author-link2= author3= author-link3= author4= author-link4= author5= author-link5= author6= author7= author8= author9= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= others= language= lang= format= website= work= publisher= via= pages= page= at= date= year= id= bibcode= doi= pmid= pmc= arxiv= archivedate= archive-date= archivebot= accessdate= access-date= quote= comment= url-status=  ref= url-access= orig-year= editor= editor-link= editor-last= editor-first= editor1-link= editor1-last= editor1-first= editor2= editor2-last= editor2-first= editor2-link= department= series= agency= location= place= publication-place= publication-date= type= asin= doi-broken-date= isbn= issn= jfm= jstor= lccn= mr= oclc= ol= osti= rfc= ssrn= zbl= postscript= df= mode= display-authors= display-editors= book-title= contribution-url=  offline= coauthors= month= authorlink2= authorlink3= authorlink4= authorlink5= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite web
   |errNS    = 0
   |template = Vorlage:Cite web
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if: Vorlage:Cite book/Webarchiv
    | Vorlage:Cite book/Meldung
  }}{{#if:  | Vorlage:Cite book/Meldung }}Vorlage:Cite book/Meldung2{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
    | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/%7C^^%7C%7C+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:2012-02-17|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:2012-01-10|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:en|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}{{#ifexpr: {{#ifeq:^^|^^|0|1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>. Die Routenlänge kann auch größer als der Durchmesser sein, da der greedy Routingalgorithmus kürzeste Pfade eventuell nicht findet<ref>Gurmeet Singh Manku, Moni Naor, Udi Wieder: "Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks". Proc. STOC, 2004.</ref>.

Algorithmen für Overlay-Netze

Neben Routing gibt es viele Algorithmen, welche die Struktur von Overlay-Netzen in DHTs ausnutzen, um Nachrichten an alle Knoten oder eine Teilmenge zu senden.<ref>Ali Ghodsi: <templatestyles src="Webarchiv/styles.css" />{{#if:20070522060750

      | {{#ifeq: 20070522060750 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20070522060750}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20070522060750}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables | {{#invoke:WLink|getEscapedTitle|Distributed k-ary System: Algorithms for Distributed Hash Tables}} | {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20070522060750|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.sics.se/~ali/thesis/}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Distributed k-ary System: Algorithms for Distributed Hash Tables
    | {{#if: {{#invoke:WLink|isBracketedLink|Distributed k-ary System: Algorithms for Distributed Hash Tables}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.sics.se/~ali/thesis/%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.sics.se/~ali/thesis/%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.sics.se/~ali/thesis/ }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}. KTH – Royal Institute of Technology, 2006.</ref> Diese Algorithmen werden von Anwendungen für Overlay-Multicasts, Range Queries oder zum Sammeln von Statistiken eingesetzt. Zwei auf diesem Ansatz basierende Systeme sind Structella<ref>{{#invoke:Vorlage:Literatur|f}}{{#if: 
       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: ACM SIGCOMM Computer Communication Review
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:Castro|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>, das Flooding und Random Walks auf einem Pastry-Overlay implementiert, sowie DQ-DHT, das einen dynamischen Query-Suchalgorithmus über einem Chord-Netzwerk implementiert.<ref>{{#invoke:Vorlage:Literatur|f}}{{#if: 
       | {{#if: Vorlage:Cite book/ParamBool
               | Vorlage:Toter Link/archivebot
               | Vorlage:Webarchiv/archiv-bot
         }}
  }}{{#invoke:TemplatePar|check
   |all    = title=
   |opt    = vauthors= author= author1= authorlink= author-link= author-link1= author1-link= author2= author3= author4= author5= author6= author7= author8= author9= editor= last= first= last1= first1= last2= first2= last3= first3= last4= first4= last5= first5= last6= first6= last7= first7= last8= first8= last9= first9= last10= first10= last11= first11= last12= first12= last13= first13= last14= first14= last15= first15= others= script-title= trans-title= date= year= volume= issue= number= series= page= pages= at= issn= arxiv= bibcode= doi= pmid= pmc= jstor= oclc= id= url= url-status= format= access-date= archive-date= archive-url= archivebot= offline= location= publisher= language= quote= work= journal= newspaper= magazine= periodical=  name-list-style= url-access= doi-access= display-authors= via= s2cid= mr= type= citeseerx=  accessdate= archivedate= archiveurl= coauthors= month= day= last16= first16= last17= first17= last18= first18= last19= first19= last20= first20= last21= first21= last22= first22= last23= first23= last24= first24= last25= first25= last26= first26= last27= first27= last28= first28= last29= first29= last30= first30= last31= first31=
   |cat      = Wikipedia:Vorlagenfehler/Vorlage:Cite journal
   |errNS    = 0
   |template = Vorlage:Cite journal
   |format   = @@@
   |preview  = 1
  }}Vorlage:Cite book/URL{{#if:  | Vorlage:Cite book/Meldung }}{{#if:        | Vorlage:Cite book/Meldung }}{{#if: Journal of Parallel and Distributed Computing
     || Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
        | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
       | Vorlage:Cite book/Meldung
  }}{{#if: Vorlage:Cite book/ParamBool
     | Vorlage:Cite book/Meldung
  }}Vorlage:Cite book/Meldung2{{#ifexpr: 0{{#ifeq:^^|^^||+1}}{{#ifeq:Talia|^^||+1}}{{#ifeq:^^|^^||+1}}{{#ifeq:^^|^^||+1}} > 1
    | Vorlage:Cite book/Meldung
  }}</ref>

Implementierungen

Auf vielen Rechnern ist das Senden von Nachrichten deutlich teurer als lokale Hashtabellen-Zugriffe. Deshalb ist eine Bündelung vieler Nachrichten in einen Batch sinnvoll. Die Nachrichten werden unter der Annahme, dass jeder Knoten einen lokalen Batch von maximal <math>b</math> Nachrichten hat, wie folgt gebündelt. Jeder Knoten sortiert seinen lokalen Batch zunächst nach der ID des für die Nachricht zuständigen Knotens. Dies ist in <math>O(b + n)</math> Zeit mit Bucketsort möglich, wobei <math>n</math> die Knotenanzahl in der DHT ist. Falls es in einem Batch mehrere Operationen für denselben Key gibt, wird der Batch noch vor dem Senden reduziert. Zum Beispiel können mehrere Anfragen für denselben Key zu einer reduziert werden oder mehrere inkrement-Operationen zu einer add-Operation. Dies kann mit einer lokalen Hashtable realisiert werden. Schließlich werden die Operationen an die jeweiligen Knoten geschickt.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Derzeit existieren unter anderem folgende Implementierungen verteilter Hashtabellen:

IPFS
Kademlia – Strukturen basierend auf diesem Algorithmus existieren in mehreren P2P-Netzwerken, sind allerdings meist nicht untereinander kompatibel. Implementierungen:
- KAD – Entwicklung des eMule-Entwicklungsteams, basierend auf dem Kademlia-Algorithmus, um die mit der Zeit ausfallenden Server des eDonkey2000-Netzwerks zu ersetzen.
- Mojito – Entwicklung des LimeWire-Entwicklungsteams zur schnellen Quellenermittlung innerhalb des Gnutella-Netzwerks.

Anwendungen

DHTs zur Datenspeicherung

Software

apt-p2p (Paketverwaltungssystem): Verteiltes Update auf Basis von apt
Vuze: BitTorrent-Client
BitComet: BitTorrent-Client
BitTorrent (ab Version 4.1.0)
Coral: Verteilungsnetzwerk für Inhalte
CSpace: Instant Messenger mit Kademlia
Deluge (BitTorrent-Client)
eDonkey2000, Name: Overnet
eMule (ab Version 0.40) und aMule (ab Version 2.1.0), Name: Kad
Free Download Manager: freier Download-Manager, der auch BitTorrent und DHT beherrscht
Freenet: Anonymer Datenspeicher.
Halite: BitTorrent-Client
KTorrent: BitTorrent-Client
LimeWire (Name: Mojito)
MLDonkey (Overnet und Kademlia)
µTorrent: BitTorrent-Client
qBittorrent: BitTorrent-Client
RetroShare: serverloser Instant Messenger, anonymes/Filesharing, Newsgroup, Voice over IP, E-Mail
rTorrent: BitTorrent-Client
Tox: Instant Messenger
Transmission (Software): BitTorrent-Client
YaCy: verteilte Suchmaschine

DHT-Forschung

{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: http://iris.csail.mit.edu/
       | {{#if: Project IRIS | Project IRIS }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2017-11-23 | , festgestellt im {{#invoke:DateTime|format|2017-11-23|F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2017-11-23 | , festgestellt im {{#invoke:DateTime|format|2017-11-23|F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: http://iris.csail.mit.edu/
      | {{#if:{{#invoke:URLutil|isWebURL|http://iris.csail.mit.edu/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: Project IRIS
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 2017-11-23
       | {{#if:{{#invoke:DateTime|format|2017-11-23|F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://iris.csail.mit.edu/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2017-11-23 | , festgestellt im {{#invoke:DateTime|format|2017-11-23|F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: http://iris.csail.mit.edu/
       | {{#if:{{#invoke:URLutil|isWebURL|http://iris.csail.mit.edu/}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 2017-11-23
         | {{#if:{{#invoke:DateTime|format|2017-11-23|F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[http://iris.csail.mit.edu/ }} (Infrastructure for Resilient Internet Systems)

Einzelnachweise