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


...