Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Indranil Gupta , Ken Birman , Prakash Linga , Al Demers , Robbert van Renesse

ABSTRACT

A peer-to-peer (p2p) distributed hash table (DHT) system allows hosts to join and fail silently (or leave), as well as to insert and retrieve files (objects). This paper explores a new point in design space in which increased memory usage and constant background communication overheads are tolerated to reduce file lookup times and increase stability to failures and churn. Our system, called Kelips, uses peer-to-peer gossip to partially replicate file index information. In Kelips, (a) under normal conditions, file lookups are resolved within 1 RPC, independent of system size, and (b) membership changes (e.g., even when a large number of nodes fail) are detected and disseminated to the system quickly. Per-node memory requirements are small in medium-sized systems. When there are failures, lookup success is ensured through query rerouting. Kelips achieves load balancing comparable to existing systems. Locality is supported by using topologically aware gossip mechanisms. Initial results of an ongoing experimental study are also discussed. More... »

PAGES

160-169

References to SciGraph publications

Book

TITLE

Peer-to-Peer Systems II

ISBN

978-3-540-40724-9
978-3-540-45172-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-45172-3_15

DOI

http://dx.doi.org/10.1007/978-3-540-45172-3_15

DIMENSIONS

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


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": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gupta", 
        "givenName": "Indranil", 
        "id": "sg:person.015320453521.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015320453521.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Birman", 
        "givenName": "Ken", 
        "id": "sg:person.012535635237.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012535635237.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Linga", 
        "givenName": "Prakash", 
        "id": "sg:person.013755435727.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013755435727.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Demers", 
        "givenName": "Al", 
        "id": "sg:person.012134057751.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012134057751.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "van Renesse", 
        "givenName": "Robbert", 
        "id": "sg:person.010501057523.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010501057523.01"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/380752.380796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000471796"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/41840.41841", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022752417"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1117/12.449977", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039039143"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/312203.312207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042100928"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-1283-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049184304", 
          "https://doi.org/10.1007/978-1-4471-1283-9_4"
        ], 
        "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/hotos.2001.990065", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093629819"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "A peer-to-peer (p2p) distributed hash table (DHT) system allows hosts to join and fail silently (or leave), as well as to insert and retrieve files (objects). This paper explores a new point in design space in which increased memory usage and constant background communication overheads are tolerated to reduce file lookup times and increase stability to failures and churn. Our system, called Kelips, uses peer-to-peer gossip to partially replicate file index information. In Kelips, (a) under normal conditions, file lookups are resolved within 1 RPC, independent of system size, and (b) membership changes (e.g., even when a large number of nodes fail) are detected and disseminated to the system quickly. Per-node memory requirements are small in medium-sized systems. When there are failures, lookup success is ensured through query rerouting. Kelips achieves load balancing comparable to existing systems. Locality is supported by using topologically aware gossip mechanisms. Initial results of an ongoing experimental study are also discussed.", 
    "editor": [
      {
        "familyName": "Kaashoek", 
        "givenName": "M. Frans", 
        "type": "Person"
      }, 
      {
        "familyName": "Stoica", 
        "givenName": "Ion", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-45172-3_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-40724-9", 
        "978-3-540-45172-3"
      ], 
      "name": "Peer-to-Peer Systems II", 
      "type": "Book"
    }, 
    "name": "Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead", 
    "pagination": "160-169", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038176093"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-45172-3_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b5dc05ed2c90c1bc5db89a7d25cf6724a167b50da34f08d58e988d5f505d6eb2"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-45172-3_15", 
      "https://app.dimensions.ai/details/publication/pub.1038176093"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:35", 
    "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/0000000365_0000000365/records_71677_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-45172-3_15"
  }
]
 

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-45172-3_15'

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-45172-3_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-45172-3_15'

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-45172-3_15'


 

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

121 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-45172-3_15 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N7f463503514144fba3966137ac51e167
4 schema:citation sg:pub.10.1007/3-540-45518-3_18
5 sg:pub.10.1007/978-1-4471-1283-9_4
6 https://doi.org/10.1109/hotos.2001.990065
7 https://doi.org/10.1117/12.449977
8 https://doi.org/10.1145/312203.312207
9 https://doi.org/10.1145/380752.380796
10 https://doi.org/10.1145/41840.41841
11 schema:datePublished 2003
12 schema:datePublishedReg 2003-01-01
13 schema:description A peer-to-peer (p2p) distributed hash table (DHT) system allows hosts to join and fail silently (or leave), as well as to insert and retrieve files (objects). This paper explores a new point in design space in which increased memory usage and constant background communication overheads are tolerated to reduce file lookup times and increase stability to failures and churn. Our system, called Kelips, uses peer-to-peer gossip to partially replicate file index information. In Kelips, (a) under normal conditions, file lookups are resolved within 1 RPC, independent of system size, and (b) membership changes (e.g., even when a large number of nodes fail) are detected and disseminated to the system quickly. Per-node memory requirements are small in medium-sized systems. When there are failures, lookup success is ensured through query rerouting. Kelips achieves load balancing comparable to existing systems. Locality is supported by using topologically aware gossip mechanisms. Initial results of an ongoing experimental study are also discussed.
14 schema:editor N64f741b1e4464d22b2e469c37509fa56
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree true
18 schema:isPartOf N2daaf456c35743a7917e08f19d31907e
19 schema:name Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead
20 schema:pagination 160-169
21 schema:productId Na2acef1db9da45dcb2b8d90db2d645b6
22 Nc3de02763ad54afb97bea39ddd3326ee
23 Nd38bf3359c3a43d4973b9bdfbe05c5bd
24 schema:publisher N335f5a30314341a28cbe89505ef1390c
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038176093
26 https://doi.org/10.1007/978-3-540-45172-3_15
27 schema:sdDatePublished 2019-04-16T08:35
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher Neafa3524fc024d52a8927335d99ade32
30 schema:url https://link.springer.com/10.1007%2F978-3-540-45172-3_15
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N1816f02b6edc449d96b22406330f9098 schema:familyName Kaashoek
35 schema:givenName M. Frans
36 rdf:type schema:Person
37 N1d57b3b03e5d467ab95886a10c64fa2f schema:familyName Stoica
38 schema:givenName Ion
39 rdf:type schema:Person
40 N2daaf456c35743a7917e08f19d31907e schema:isbn 978-3-540-40724-9
41 978-3-540-45172-3
42 schema:name Peer-to-Peer Systems II
43 rdf:type schema:Book
44 N335f5a30314341a28cbe89505ef1390c schema:location Berlin, Heidelberg
45 schema:name Springer Berlin Heidelberg
46 rdf:type schema:Organisation
47 N39aedfe77d71488da72053b437694090 rdf:first N1d57b3b03e5d467ab95886a10c64fa2f
48 rdf:rest rdf:nil
49 N52529a98c5a142d2bfa1d026263ae644 rdf:first sg:person.010501057523.01
50 rdf:rest rdf:nil
51 N64f741b1e4464d22b2e469c37509fa56 rdf:first N1816f02b6edc449d96b22406330f9098
52 rdf:rest N39aedfe77d71488da72053b437694090
53 N6e7610e978224b28ba543f6c5fbec938 rdf:first sg:person.012535635237.39
54 rdf:rest Nafb5cbd9a5ce4925a5afdc2563920ad2
55 N7f463503514144fba3966137ac51e167 rdf:first sg:person.015320453521.31
56 rdf:rest N6e7610e978224b28ba543f6c5fbec938
57 Na2acef1db9da45dcb2b8d90db2d645b6 schema:name dimensions_id
58 schema:value pub.1038176093
59 rdf:type schema:PropertyValue
60 Nafb5cbd9a5ce4925a5afdc2563920ad2 rdf:first sg:person.013755435727.06
61 rdf:rest Nbe1215bfdbc046bfa23812015d292af4
62 Nbe1215bfdbc046bfa23812015d292af4 rdf:first sg:person.012134057751.06
63 rdf:rest N52529a98c5a142d2bfa1d026263ae644
64 Nc3de02763ad54afb97bea39ddd3326ee schema:name readcube_id
65 schema:value b5dc05ed2c90c1bc5db89a7d25cf6724a167b50da34f08d58e988d5f505d6eb2
66 rdf:type schema:PropertyValue
67 Nd38bf3359c3a43d4973b9bdfbe05c5bd schema:name doi
68 schema:value 10.1007/978-3-540-45172-3_15
69 rdf:type schema:PropertyValue
70 Neafa3524fc024d52a8927335d99ade32 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
73 schema:name Information and Computing Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
76 schema:name Computer Software
77 rdf:type schema:DefinedTerm
78 sg:person.010501057523.01 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
79 schema:familyName van Renesse
80 schema:givenName Robbert
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010501057523.01
82 rdf:type schema:Person
83 sg:person.012134057751.06 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
84 schema:familyName Demers
85 schema:givenName Al
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012134057751.06
87 rdf:type schema:Person
88 sg:person.012535635237.39 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
89 schema:familyName Birman
90 schema:givenName Ken
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012535635237.39
92 rdf:type schema:Person
93 sg:person.013755435727.06 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
94 schema:familyName Linga
95 schema:givenName Prakash
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013755435727.06
97 rdf:type schema:Person
98 sg:person.015320453521.31 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
99 schema:familyName Gupta
100 schema:givenName Indranil
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015320453521.31
102 rdf:type schema:Person
103 sg:pub.10.1007/3-540-45518-3_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051261708
104 https://doi.org/10.1007/3-540-45518-3_18
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-1-4471-1283-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049184304
107 https://doi.org/10.1007/978-1-4471-1283-9_4
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1109/hotos.2001.990065 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093629819
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1117/12.449977 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039039143
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/312203.312207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042100928
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/380752.380796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000471796
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/41840.41841 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022752417
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.5386.8 schema:alternateName Cornell University
120 schema:name Cornell University, Ithaca, NY, USA
121 rdf:type schema:Organization
 




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


...