Distributed Maintenance of a Spanning Tree Using Labeled Tree Encoding View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Vijay K. Garg , Anurag Agarwal

ABSTRACT

Maintaining spanning trees in a distributed fashion is central to many networking applications. In this paper, we propose a self-stabilizing algorithm for maintaining a spanning tree in a distributed fashion for a completely connected topology. Our algorithm requires a node to process O(1) messages of size O(log n) on average in one cycle as compared to previous algorithms which need to process messages from every neighbor, resulting in O(n) work in a completely connected topology. Our algorithm also stabilizes faster than the previous approaches. More... »

PAGES

606-616

Book

TITLE

Euro-Par 2005 Parallel Processing

ISBN

978-3-540-28700-1
978-3-540-31925-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11549468_68

DOI

http://dx.doi.org/10.1007/11549468_68

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "The University of Texas at Austin", 
          "id": "https://www.grid.ac/institutes/grid.89336.37", 
          "name": [
            "University of Texas at Austin, 78712-1084, Austin, TX"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garg", 
        "givenName": "Vijay K.", 
        "id": "sg:person.014441462141.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014441462141.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "The University of Texas at Austin", 
          "id": "https://www.grid.ac/institutes/grid.89336.37", 
          "name": [
            "University of Texas at Austin, 78712-1084, Austin, TX"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Agarwal", 
        "givenName": "Anurag", 
        "id": "sg:person.011763364675.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011763364675.48"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bfb0002773", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002982212", 
          "https://doi.org/10.1007/bfb0002773"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/361179.361202", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005796851"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-54099-7_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026434595", 
          "https://doi.org/10.1007/3-540-54099-7_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-57529-4_72", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035925902", 
          "https://doi.org/10.1007/3-540-57529-4_72"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/259380.259508", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037236322"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(92)90264-v", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038918704"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(94)90103-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040383730"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s030500410002853x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054084145"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/12.312126", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061087983"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/eeis.1989.720146", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086233114"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/eeis.1989.720146", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086233114"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1991.185378", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086290493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511814075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098701235"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/93385.93407", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1099022743"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1111385890", 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Maintaining spanning trees in a distributed fashion is central to many networking applications. In this paper, we propose a self-stabilizing algorithm for maintaining a spanning tree in a distributed fashion for a completely connected topology. Our algorithm requires a node to process O(1) messages of size O(log n) on average in one cycle as compared to previous algorithms which need to process messages from every neighbor, resulting in O(n) work in a completely connected topology. Our algorithm also stabilizes faster than the previous approaches.", 
    "editor": [
      {
        "familyName": "Cunha", 
        "givenName": "Jos\u00e9 C.", 
        "type": "Person"
      }, 
      {
        "familyName": "Medeiros", 
        "givenName": "Pedro D.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11549468_68", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28700-1", 
        "978-3-540-31925-2"
      ], 
      "name": "Euro-Par 2005 Parallel Processing", 
      "type": "Book"
    }, 
    "name": "Distributed Maintenance of a Spanning Tree Using Labeled Tree Encoding", 
    "pagination": "606-616", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014293617"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11549468_68"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4418265728d24b6190cb307f6905a2ae5505d233f6dce27e7f50d68c54f51c81"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11549468_68", 
      "https://app.dimensions.ai/details/publication/pub.1014293617"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:24", 
    "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_70046_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F11549468_68"
  }
]
 

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/11549468_68'

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/11549468_68'

Turtle is a human-readable linked data format.

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

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

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


 

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

121 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11549468_68 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N828c760033234275b843fb57e7bdf46d
4 schema:citation sg:pub.10.1007/3-540-54099-7_2
5 sg:pub.10.1007/3-540-57529-4_72
6 sg:pub.10.1007/bfb0002773
7 https://app.dimensions.ai/details/publication/pub.1111385890
8 https://doi.org/10.1016/0020-0190(92)90264-v
9 https://doi.org/10.1016/0020-0190(94)90103-1
10 https://doi.org/10.1017/cbo9780511814075
11 https://doi.org/10.1017/s030500410002853x
12 https://doi.org/10.1109/12.312126
13 https://doi.org/10.1109/eeis.1989.720146
14 https://doi.org/10.1109/sfcs.1991.185378
15 https://doi.org/10.1145/259380.259508
16 https://doi.org/10.1145/361179.361202
17 https://doi.org/10.1145/93385.93407
18 schema:datePublished 2005
19 schema:datePublishedReg 2005-01-01
20 schema:description Maintaining spanning trees in a distributed fashion is central to many networking applications. In this paper, we propose a self-stabilizing algorithm for maintaining a spanning tree in a distributed fashion for a completely connected topology. Our algorithm requires a node to process O(1) messages of size O(log n) on average in one cycle as compared to previous algorithms which need to process messages from every neighbor, resulting in O(n) work in a completely connected topology. Our algorithm also stabilizes faster than the previous approaches.
21 schema:editor N1ed1d3cbc0744f4eab27c949d8da4b6e
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N674cf3ed4aa04029a0cc0d31867811aa
26 schema:name Distributed Maintenance of a Spanning Tree Using Labeled Tree Encoding
27 schema:pagination 606-616
28 schema:productId N001ff931251a4f4dad17c911f9c93246
29 N5175712ffa37441ba65b196dff2e487d
30 Nb2ad17fcc62d4b9d949a1a37f61914fd
31 schema:publisher N860fbf0c3e1d4394b9f3dbc07788431d
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014293617
33 https://doi.org/10.1007/11549468_68
34 schema:sdDatePublished 2019-04-16T08:24
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N9a27674c4eef4ab2851bc2be7671c553
37 schema:url https://link.springer.com/10.1007%2F11549468_68
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N001ff931251a4f4dad17c911f9c93246 schema:name readcube_id
42 schema:value 4418265728d24b6190cb307f6905a2ae5505d233f6dce27e7f50d68c54f51c81
43 rdf:type schema:PropertyValue
44 N011641c5689349e2b761eb5430327fe9 rdf:first sg:person.011763364675.48
45 rdf:rest rdf:nil
46 N1ed1d3cbc0744f4eab27c949d8da4b6e rdf:first Nfdb1ddcd63a347e79a0ba4701b6cd8e8
47 rdf:rest N7fdb719287e8436585c2f18fd163ca76
48 N5175712ffa37441ba65b196dff2e487d schema:name dimensions_id
49 schema:value pub.1014293617
50 rdf:type schema:PropertyValue
51 N674cf3ed4aa04029a0cc0d31867811aa schema:isbn 978-3-540-28700-1
52 978-3-540-31925-2
53 schema:name Euro-Par 2005 Parallel Processing
54 rdf:type schema:Book
55 N7fdb719287e8436585c2f18fd163ca76 rdf:first Nae592b6b59564f72b1509483a76f7e67
56 rdf:rest rdf:nil
57 N828c760033234275b843fb57e7bdf46d rdf:first sg:person.014441462141.17
58 rdf:rest N011641c5689349e2b761eb5430327fe9
59 N860fbf0c3e1d4394b9f3dbc07788431d schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 N9a27674c4eef4ab2851bc2be7671c553 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nae592b6b59564f72b1509483a76f7e67 schema:familyName Medeiros
65 schema:givenName Pedro D.
66 rdf:type schema:Person
67 Nb2ad17fcc62d4b9d949a1a37f61914fd schema:name doi
68 schema:value 10.1007/11549468_68
69 rdf:type schema:PropertyValue
70 Nfdb1ddcd63a347e79a0ba4701b6cd8e8 schema:familyName Cunha
71 schema:givenName José C.
72 rdf:type schema:Person
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
77 schema:name Computation Theory and Mathematics
78 rdf:type schema:DefinedTerm
79 sg:person.011763364675.48 schema:affiliation https://www.grid.ac/institutes/grid.89336.37
80 schema:familyName Agarwal
81 schema:givenName Anurag
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011763364675.48
83 rdf:type schema:Person
84 sg:person.014441462141.17 schema:affiliation https://www.grid.ac/institutes/grid.89336.37
85 schema:familyName Garg
86 schema:givenName Vijay K.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014441462141.17
88 rdf:type schema:Person
89 sg:pub.10.1007/3-540-54099-7_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026434595
90 https://doi.org/10.1007/3-540-54099-7_2
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/3-540-57529-4_72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035925902
93 https://doi.org/10.1007/3-540-57529-4_72
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bfb0002773 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002982212
96 https://doi.org/10.1007/bfb0002773
97 rdf:type schema:CreativeWork
98 https://app.dimensions.ai/details/publication/pub.1111385890 schema:CreativeWork
99 https://doi.org/10.1016/0020-0190(92)90264-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1038918704
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/0020-0190(94)90103-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040383730
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1017/cbo9780511814075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098701235
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1017/s030500410002853x schema:sameAs https://app.dimensions.ai/details/publication/pub.1054084145
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1109/12.312126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061087983
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1109/eeis.1989.720146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086233114
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1109/sfcs.1991.185378 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086290493
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/259380.259508 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037236322
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1145/361179.361202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005796851
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/93385.93407 schema:sameAs https://app.dimensions.ai/details/publication/pub.1099022743
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.89336.37 schema:alternateName The University of Texas at Austin
120 schema:name University of Texas at Austin, 78712-1084, Austin, TX
121 rdf:type schema:Organization
 




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


...