Comparing the Performance of Distributed Hash Tables Under Churn View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Jinyang Li , Jeremy Stribling , Thomer M. Gil , Robert Morris , M. Frans Kaashoek

ABSTRACT

A protocol for a distributed hash table (DHT) incurs communication costs to keep up with churn – changes in membership – in order to maintain its ability to route lookups efficiently. This paper formulates a unified framework for evaluating cost and performance. Communication costs are combined into a single cost measure (bytes), and performance benefits are reduced to a single latency measure. This approach correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost. Using the unified framework, this paper analyzes the effects of DHT parameters on the performance of four protocols under churn. More... »

PAGES

87-99

References to SciGraph publications

Book

TITLE

Peer-to-Peer Systems III

ISBN

978-3-540-24252-9
978-3-540-30183-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30183-7_9

DOI

http://dx.doi.org/10.1007/978-3-540-30183-7_9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1043575988


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Jinyang", 
        "id": "sg:person.011307616677.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011307616677.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stribling", 
        "givenName": "Jeremy", 
        "id": "sg:person.011756245111.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011756245111.61"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gil", 
        "givenName": "Thomer M.", 
        "id": "sg:person.014206646663.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014206646663.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Morris", 
        "givenName": "Robert", 
        "id": "sg:person.01106062524.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01106062524.61"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaashoek", 
        "givenName": "M. Frans", 
        "id": "sg:person.011353220467.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011353220467.59"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/571825.571863", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008579550"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/b11823", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009724176", 
          "https://doi.org/10.1007/b11823"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/b11823", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009724176", 
          "https://doi.org/10.1007/b11823"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45172-3_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015681279", 
          "https://doi.org/10.1007/978-3-540-45172-3_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45172-3_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015681279", 
          "https://doi.org/10.1007/978-3-540-45172-3_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/571825.571857", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016069079"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/863955.863998", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036272214"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00530-003-0088-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037261978", 
          "https://doi.org/10.1007/s00530-003-0088-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45172-3_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038176093", 
          "https://doi.org/10.1007/978-3-540-45172-3_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-45172-3_15", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038176093", 
          "https://doi.org/10.1007/978-3-540-45172-3_15"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45748-8_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040097069", 
          "https://doi.org/10.1007/3-540-45748-8_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45748-8_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040097069", 
          "https://doi.org/10.1007/3-540-45748-8_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/637201.637203", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049868919"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45518-3_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051261708", 
          "https://doi.org/10.1007/3-540-45518-3_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45518-3_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051261708", 
          "https://doi.org/10.1007/3-540-45518-3_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/jsac.2003.818784", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061316503"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2003.1209238", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093459980"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/dsn.2004.1311872", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095397260"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "A protocol for a distributed hash table (DHT) incurs communication costs to keep up with churn \u2013 changes in membership \u2013 in order to maintain its ability to route lookups efficiently. This paper formulates a unified framework for evaluating cost and performance. Communication costs are combined into a single cost measure (bytes), and performance benefits are reduced to a single latency measure. This approach correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost. Using the unified framework, this paper analyzes the effects of DHT parameters on the performance of four protocols under churn.", 
    "editor": [
      {
        "familyName": "Voelker", 
        "givenName": "Geoffrey M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Shenker", 
        "givenName": "Scott", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30183-7_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24252-9", 
        "978-3-540-30183-7"
      ], 
      "name": "Peer-to-Peer Systems III", 
      "type": "Book"
    }, 
    "name": "Comparing the Performance of Distributed Hash Tables Under Churn", 
    "pagination": "87-99", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043575988"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30183-7_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "cf91756b68e7e0ef8300a2a0cd51cbd8c5a3dee0848ceac0c5c8324febd72544"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30183-7_9", 
      "https://app.dimensions.ai/details/publication/pub.1043575988"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:22", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70032_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-30183-7_9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30183-7_9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30183-7_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30183-7_9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30183-7_9'


 

This table displays all metadata directly associated to this object as RDF triples.

143 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30183-7_9 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author Nb8acdc3a10f940c09335a31f4f4b7782
4 schema:citation sg:pub.10.1007/3-540-45518-3_18
5 sg:pub.10.1007/3-540-45748-8_5
6 sg:pub.10.1007/978-3-540-45172-3_15
7 sg:pub.10.1007/978-3-540-45172-3_5
8 sg:pub.10.1007/b11823
9 sg:pub.10.1007/s00530-003-0088-1
10 https://doi.org/10.1109/dsn.2004.1311872
11 https://doi.org/10.1109/infcom.2003.1209238
12 https://doi.org/10.1109/jsac.2003.818784
13 https://doi.org/10.1145/571825.571857
14 https://doi.org/10.1145/571825.571863
15 https://doi.org/10.1145/637201.637203
16 https://doi.org/10.1145/863955.863998
17 schema:datePublished 2005
18 schema:datePublishedReg 2005-01-01
19 schema:description A protocol for a distributed hash table (DHT) incurs communication costs to keep up with churn – changes in membership – in order to maintain its ability to route lookups efficiently. This paper formulates a unified framework for evaluating cost and performance. Communication costs are combined into a single cost measure (bytes), and performance benefits are reduced to a single latency measure. This approach correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost. Using the unified framework, this paper analyzes the effects of DHT parameters on the performance of four protocols under churn.
20 schema:editor Ndf9b143e85b9462380e6f5d3d0d0ecf8
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N48f8a2b096fe4e03b34e474451877203
25 schema:name Comparing the Performance of Distributed Hash Tables Under Churn
26 schema:pagination 87-99
27 schema:productId N4d8164541f394c348a949befe0449441
28 N5162d55c8b634a7c9aa1a9437ed54e23
29 Ne50542648444468c95b9210fa9785292
30 schema:publisher Nb3a8c9bafc274c4987ff0e2ee7b2a15c
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043575988
32 https://doi.org/10.1007/978-3-540-30183-7_9
33 schema:sdDatePublished 2019-04-16T08:22
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher N83e0c2b3c37c4eb39f61a6183efb8909
36 schema:url https://link.springer.com/10.1007%2F978-3-540-30183-7_9
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N069c403cd64e441983346bdceedba2df schema:familyName Shenker
41 schema:givenName Scott
42 rdf:type schema:Person
43 N3bb83db726334a4cb04f7b05f7ca5734 rdf:first sg:person.011756245111.61
44 rdf:rest N447e555b884a41bb9199137c45c50eb3
45 N447e555b884a41bb9199137c45c50eb3 rdf:first sg:person.014206646663.57
46 rdf:rest Nd37ddb76cdcc4c1590ad9c93ffe4f10d
47 N48f8a2b096fe4e03b34e474451877203 schema:isbn 978-3-540-24252-9
48 978-3-540-30183-7
49 schema:name Peer-to-Peer Systems III
50 rdf:type schema:Book
51 N4d8164541f394c348a949befe0449441 schema:name readcube_id
52 schema:value cf91756b68e7e0ef8300a2a0cd51cbd8c5a3dee0848ceac0c5c8324febd72544
53 rdf:type schema:PropertyValue
54 N5162d55c8b634a7c9aa1a9437ed54e23 schema:name doi
55 schema:value 10.1007/978-3-540-30183-7_9
56 rdf:type schema:PropertyValue
57 N6083ac2587aa410ba006579862777161 rdf:first sg:person.011353220467.59
58 rdf:rest rdf:nil
59 N83e0c2b3c37c4eb39f61a6183efb8909 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nb3a8c9bafc274c4987ff0e2ee7b2a15c schema:location Berlin, Heidelberg
62 schema:name Springer Berlin Heidelberg
63 rdf:type schema:Organisation
64 Nb8acdc3a10f940c09335a31f4f4b7782 rdf:first sg:person.011307616677.92
65 rdf:rest N3bb83db726334a4cb04f7b05f7ca5734
66 Ncea178465e504519a65d7e50ea0f0c50 rdf:first N069c403cd64e441983346bdceedba2df
67 rdf:rest rdf:nil
68 Nd37ddb76cdcc4c1590ad9c93ffe4f10d rdf:first sg:person.01106062524.61
69 rdf:rest N6083ac2587aa410ba006579862777161
70 Nd72dd375a66e40bb89409f7662a76bcf schema:familyName Voelker
71 schema:givenName Geoffrey M.
72 rdf:type schema:Person
73 Ndf9b143e85b9462380e6f5d3d0d0ecf8 rdf:first Nd72dd375a66e40bb89409f7662a76bcf
74 rdf:rest Ncea178465e504519a65d7e50ea0f0c50
75 Ne50542648444468c95b9210fa9785292 schema:name dimensions_id
76 schema:value pub.1043575988
77 rdf:type schema:PropertyValue
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
82 schema:name Computer Software
83 rdf:type schema:DefinedTerm
84 sg:person.01106062524.61 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
85 schema:familyName Morris
86 schema:givenName Robert
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01106062524.61
88 rdf:type schema:Person
89 sg:person.011307616677.92 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
90 schema:familyName Li
91 schema:givenName Jinyang
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011307616677.92
93 rdf:type schema:Person
94 sg:person.011353220467.59 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
95 schema:familyName Kaashoek
96 schema:givenName M. Frans
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011353220467.59
98 rdf:type schema:Person
99 sg:person.011756245111.61 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
100 schema:familyName Stribling
101 schema:givenName Jeremy
102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011756245111.61
103 rdf:type schema:Person
104 sg:person.014206646663.57 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
105 schema:familyName Gil
106 schema:givenName Thomer M.
107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014206646663.57
108 rdf:type schema:Person
109 sg:pub.10.1007/3-540-45518-3_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051261708
110 https://doi.org/10.1007/3-540-45518-3_18
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/3-540-45748-8_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040097069
113 https://doi.org/10.1007/3-540-45748-8_5
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-3-540-45172-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038176093
116 https://doi.org/10.1007/978-3-540-45172-3_15
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/978-3-540-45172-3_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015681279
119 https://doi.org/10.1007/978-3-540-45172-3_5
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/b11823 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009724176
122 https://doi.org/10.1007/b11823
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/s00530-003-0088-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037261978
125 https://doi.org/10.1007/s00530-003-0088-1
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1109/dsn.2004.1311872 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095397260
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1109/infcom.2003.1209238 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093459980
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1109/jsac.2003.818784 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061316503
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1145/571825.571857 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016069079
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1145/571825.571863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008579550
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1145/637201.637203 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049868919
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1145/863955.863998 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036272214
140 rdf:type schema:CreativeWork
141 https://www.grid.ac/institutes/grid.116068.8 schema:alternateName Massachusetts Institute of Technology
142 schema:name MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA
143 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...