A Statistical Theory of Chord Under Churn View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Supriya Krishnamurthy , Sameh El-Ansary , Erik Aurell , Seif Haridi

ABSTRACT

Most earlier studies of DHTs under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different ’types’ and the implications this will have for the functioning of DHTs in general. More... »

PAGES

93-103

References to SciGraph publications

Book

TITLE

Peer-to-Peer Systems IV

ISBN

978-3-540-29068-1
978-3-540-31906-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11558989_9

DOI

http://dx.doi.org/10.1007/11558989_9

DIMENSIONS

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


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/0307", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Theoretical and Computational Chemistry", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/03", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Chemical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Swedish Institute of Computer Science", 
          "id": "https://www.grid.ac/institutes/grid.6383.e", 
          "name": [
            "Swedish Institute of Computer Science, Kista, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Krishnamurthy", 
        "givenName": "Supriya", 
        "id": "sg:person.0770637044.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0770637044.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swedish Institute of Computer Science", 
          "id": "https://www.grid.ac/institutes/grid.6383.e", 
          "name": [
            "Swedish Institute of Computer Science, Kista, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "El-Ansary", 
        "givenName": "Sameh", 
        "id": "sg:person.014453654471.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014453654471.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "Department of Physics, KTH-Royal Institute of Technology, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aurell", 
        "givenName": "Erik", 
        "id": "sg:person.01104576776.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104576776.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "IMIT-Royal Institute of Technology, Kista, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Haridi", 
        "givenName": "Seif", 
        "id": "sg:person.016533035674.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016533035674.38"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/964723.383071", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007460835"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/571825.571863", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008579550"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/571825.571862", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025066360"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30183-7_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043575988", 
          "https://doi.org/10.1007/978-3-540-30183-7_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-30183-7_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043575988", 
          "https://doi.org/10.1007/978-3-540-30183-7_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tkde.2004.1318567", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061661292"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tnet.2002.808407", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061714344"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/glocom.2003.1258952", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093345687"
        ], 
        "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": "Most earlier studies of DHTs under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different \u2019types\u2019 and the implications this will have for the functioning of DHTs in general.", 
    "editor": [
      {
        "familyName": "Castro", 
        "givenName": "Miguel", 
        "type": "Person"
      }, 
      {
        "familyName": "van Renesse", 
        "givenName": "Robbert", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11558989_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29068-1", 
        "978-3-540-31906-1"
      ], 
      "name": "Peer-to-Peer Systems IV", 
      "type": "Book"
    }, 
    "name": "A Statistical Theory of Chord Under Churn", 
    "pagination": "93-103", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046109308"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11558989_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dba3c39f5c2446c8b8c2de583226081ebcb33cfc7a5f8370e1905889694afd6c"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11558989_9", 
      "https://app.dimensions.ai/details/publication/pub.1046109308"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:09", 
    "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/0000000360_0000000360/records_118324_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11558989_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/11558989_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/11558989_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11558989_9'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11558989_9'


 

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

120 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11558989_9 schema:about anzsrc-for:03
2 anzsrc-for:0307
3 schema:author Nf3cd5aba88204888b0af4607b081a902
4 schema:citation sg:pub.10.1007/978-3-540-30183-7_9
5 https://doi.org/10.1109/dsn.2004.1311872
6 https://doi.org/10.1109/glocom.2003.1258952
7 https://doi.org/10.1109/tkde.2004.1318567
8 https://doi.org/10.1109/tnet.2002.808407
9 https://doi.org/10.1145/571825.571862
10 https://doi.org/10.1145/571825.571863
11 https://doi.org/10.1145/964723.383071
12 schema:datePublished 2005
13 schema:datePublishedReg 2005-01-01
14 schema:description Most earlier studies of DHTs under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different ’types’ and the implications this will have for the functioning of DHTs in general.
15 schema:editor Nb29752a483eb4096ae5b3ede1d03c834
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Nffdab2069b204dd8b596ab1104fee798
20 schema:name A Statistical Theory of Chord Under Churn
21 schema:pagination 93-103
22 schema:productId N3d2ccc2fc99d4780ac3bf3745ebd1b9a
23 N8d41e4ef4059461fabe4410eeb6e0c19
24 Neb3954bb4ed84c16b378b5c56e8f0e3f
25 schema:publisher N7976427a38c74ac9b4962312085159ed
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046109308
27 https://doi.org/10.1007/11558989_9
28 schema:sdDatePublished 2019-04-16T08:09
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Ne144dc197d7743719ab30496be528e9c
31 schema:url https://link.springer.com/10.1007%2F11558989_9
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N1c30ce68b9824c2ca5fabb08408b02ef rdf:first sg:person.01104576776.49
36 rdf:rest N67f3d825d2604d7f9f466f2311b0e788
37 N3d2ccc2fc99d4780ac3bf3745ebd1b9a schema:name doi
38 schema:value 10.1007/11558989_9
39 rdf:type schema:PropertyValue
40 N5bb6b1ebba9f4bc0a89ec08dc086bf91 rdf:first Nb6077fb05b2b41e08e9554909c1ee51a
41 rdf:rest rdf:nil
42 N67f3d825d2604d7f9f466f2311b0e788 rdf:first sg:person.016533035674.38
43 rdf:rest rdf:nil
44 N7976427a38c74ac9b4962312085159ed schema:location Berlin, Heidelberg
45 schema:name Springer Berlin Heidelberg
46 rdf:type schema:Organisation
47 N7f820ac513074cbaae59cb0a2c393d7e schema:familyName Castro
48 schema:givenName Miguel
49 rdf:type schema:Person
50 N8acb3d66eafb444287b09d32178a9161 rdf:first sg:person.014453654471.34
51 rdf:rest N1c30ce68b9824c2ca5fabb08408b02ef
52 N8d41e4ef4059461fabe4410eeb6e0c19 schema:name dimensions_id
53 schema:value pub.1046109308
54 rdf:type schema:PropertyValue
55 Nb29752a483eb4096ae5b3ede1d03c834 rdf:first N7f820ac513074cbaae59cb0a2c393d7e
56 rdf:rest N5bb6b1ebba9f4bc0a89ec08dc086bf91
57 Nb6077fb05b2b41e08e9554909c1ee51a schema:familyName van Renesse
58 schema:givenName Robbert
59 rdf:type schema:Person
60 Ne144dc197d7743719ab30496be528e9c schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Neb3954bb4ed84c16b378b5c56e8f0e3f schema:name readcube_id
63 schema:value dba3c39f5c2446c8b8c2de583226081ebcb33cfc7a5f8370e1905889694afd6c
64 rdf:type schema:PropertyValue
65 Nf3cd5aba88204888b0af4607b081a902 rdf:first sg:person.0770637044.27
66 rdf:rest N8acb3d66eafb444287b09d32178a9161
67 Nffdab2069b204dd8b596ab1104fee798 schema:isbn 978-3-540-29068-1
68 978-3-540-31906-1
69 schema:name Peer-to-Peer Systems IV
70 rdf:type schema:Book
71 anzsrc-for:03 schema:inDefinedTermSet anzsrc-for:
72 schema:name Chemical Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0307 schema:inDefinedTermSet anzsrc-for:
75 schema:name Theoretical and Computational Chemistry
76 rdf:type schema:DefinedTerm
77 sg:person.01104576776.49 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
78 schema:familyName Aurell
79 schema:givenName Erik
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104576776.49
81 rdf:type schema:Person
82 sg:person.014453654471.34 schema:affiliation https://www.grid.ac/institutes/grid.6383.e
83 schema:familyName El-Ansary
84 schema:givenName Sameh
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014453654471.34
86 rdf:type schema:Person
87 sg:person.016533035674.38 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
88 schema:familyName Haridi
89 schema:givenName Seif
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016533035674.38
91 rdf:type schema:Person
92 sg:person.0770637044.27 schema:affiliation https://www.grid.ac/institutes/grid.6383.e
93 schema:familyName Krishnamurthy
94 schema:givenName Supriya
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0770637044.27
96 rdf:type schema:Person
97 sg:pub.10.1007/978-3-540-30183-7_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043575988
98 https://doi.org/10.1007/978-3-540-30183-7_9
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1109/dsn.2004.1311872 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095397260
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1109/glocom.2003.1258952 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093345687
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1109/tkde.2004.1318567 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061661292
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1109/tnet.2002.808407 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061714344
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1145/571825.571862 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025066360
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1145/571825.571863 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008579550
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/964723.383071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007460835
113 rdf:type schema:CreativeWork
114 https://www.grid.ac/institutes/grid.5037.1 schema:alternateName Royal Institute of Technology
115 schema:name Department of Physics, KTH-Royal Institute of Technology, Sweden
116 IMIT-Royal Institute of Technology, Kista, Sweden
117 rdf:type schema:Organization
118 https://www.grid.ac/institutes/grid.6383.e schema:alternateName Swedish Institute of Computer Science
119 schema:name Swedish Institute of Computer Science, Kista, Sweden
120 rdf:type schema:Organization
 




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


...