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 N4b6edddbbbd743ef9f3c126d2853444f
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 N98a246d8f8fa4badb24fd5e1a9dd9842
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf N9b647e8bbb744324a48f54e35919982c
20 schema:name A Statistical Theory of Chord Under Churn
21 schema:pagination 93-103
22 schema:productId N4a7bfc5bcadb4dae9386e7128dcc1d9c
23 N7a79efe7b71a4b4c8d70669526e4343b
24 Ndc5159f709fc44608d77265ad0078dae
25 schema:publisher N6ec68c4d6bc14affad6835388248d05e
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 N2a85d0907839465ba4dbeeb759988ed5
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 N11d9dc2b35114a8ab856b2b469a8824f rdf:first sg:person.016533035674.38
36 rdf:rest rdf:nil
37 N2a85d0907839465ba4dbeeb759988ed5 schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N3e56670042bf46fab9821f200d437327 schema:familyName Castro
40 schema:givenName Miguel
41 rdf:type schema:Person
42 N45472cd1b0b44f7cb62a4d7c55587ba8 rdf:first sg:person.014453654471.34
43 rdf:rest Nd378a08206c54ecc83ca5c9faec60736
44 N4a7bfc5bcadb4dae9386e7128dcc1d9c schema:name doi
45 schema:value 10.1007/11558989_9
46 rdf:type schema:PropertyValue
47 N4b6edddbbbd743ef9f3c126d2853444f rdf:first sg:person.0770637044.27
48 rdf:rest N45472cd1b0b44f7cb62a4d7c55587ba8
49 N6ec68c4d6bc14affad6835388248d05e schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 N7a79efe7b71a4b4c8d70669526e4343b schema:name readcube_id
53 schema:value dba3c39f5c2446c8b8c2de583226081ebcb33cfc7a5f8370e1905889694afd6c
54 rdf:type schema:PropertyValue
55 N98a246d8f8fa4badb24fd5e1a9dd9842 rdf:first N3e56670042bf46fab9821f200d437327
56 rdf:rest Nad758343152242fdb71895583298ffcb
57 N9b647e8bbb744324a48f54e35919982c schema:isbn 978-3-540-29068-1
58 978-3-540-31906-1
59 schema:name Peer-to-Peer Systems IV
60 rdf:type schema:Book
61 Nad758343152242fdb71895583298ffcb rdf:first Nc42a32601ae642f99422ef0d9d8e94c9
62 rdf:rest rdf:nil
63 Nc42a32601ae642f99422ef0d9d8e94c9 schema:familyName van Renesse
64 schema:givenName Robbert
65 rdf:type schema:Person
66 Nd378a08206c54ecc83ca5c9faec60736 rdf:first sg:person.01104576776.49
67 rdf:rest N11d9dc2b35114a8ab856b2b469a8824f
68 Ndc5159f709fc44608d77265ad0078dae schema:name dimensions_id
69 schema:value pub.1046109308
70 rdf:type schema:PropertyValue
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)


...