Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Arnaud Casteigts , Serge Chaumette , Frédéric Guinand , Yoann Pigné

ABSTRACT

We address the problem of building and maintaining a forest of spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or existence of a unique root in each fragment regardless of the events, so as to keep these fragments functioning uninterruptedly to a possible extent. Our algorithm operates at a coarse-grain level, using atomic pairwise interactions akin to population protocol or graph relabeling systems. The algorithm relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk inside the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both merging and splitting are purely localized phenomenons. This paper presents the algorithm and establishes its correctness in arbitrary dynamic networks. We also discuss aspects related to the implementation of this general principle in fine-grain models, as well as embryonic elements of analysis. The characterization of the algorithm performance is left open, both analytically and experimentally. More... »

PAGES

99-110

References to SciGraph publications

Book

TITLE

Ad-hoc, Mobile, and Wireless Network

ISBN

978-3-642-39246-7
978-3-642-39247-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39247-4_9

DOI

http://dx.doi.org/10.1007/978-3-642-39247-4_9

DIMENSIONS

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


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/0705", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Forestry Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/07", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Agricultural and Veterinary Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Bordeaux", 
          "id": "https://www.grid.ac/institutes/grid.412041.2", 
          "name": [
            "LaBRI, University of Bordeaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Casteigts", 
        "givenName": "Arnaud", 
        "id": "sg:person.014046062661.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Bordeaux", 
          "id": "https://www.grid.ac/institutes/grid.412041.2", 
          "name": [
            "LaBRI, University of Bordeaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chaumette", 
        "givenName": "Serge", 
        "id": "sg:person.015133652052.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015133652052.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "LITIS, University of Le Havre, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Guinand", 
        "givenName": "Fr\u00e9d\u00e9ric", 
        "id": "sg:person.013475656450.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013475656450.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "LITIS, University of Le Havre, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pign\u00e9", 
        "givenName": "Yoann", 
        "id": "sg:person.012016610513.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012016610513.97"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0743-7315(02)00028-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009725741"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/863955.863960", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018982547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/167088.167256", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034686486"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2332432.2332440", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042858093"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-005-0138-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047674948", 
          "https://doi.org/10.1007/s00446-005-0138-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-005-0138-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047674948", 
          "https://doi.org/10.1007/s00446-005-0138-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-75142-7_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051561882", 
          "https://doi.org/10.1007/978-3-540-75142-7_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-75142-7_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051561882", 
          "https://doi.org/10.1007/978-3-540-75142-7_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/mnet.2004.1337732", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061411423"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0403039", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844630"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/iceis.2006.1703205", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094587677"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719772", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098557268"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We address the problem of building and maintaining a forest of spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or existence of a unique root in each fragment regardless of the events, so as to keep these fragments functioning uninterruptedly to a possible extent. Our algorithm operates at a coarse-grain level, using atomic pairwise interactions akin to population protocol or graph relabeling systems. The algorithm relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk inside the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both merging and splitting are purely localized phenomenons. This paper presents the algorithm and establishes its correctness in arbitrary dynamic networks. We also discuss aspects related to the implementation of this general principle in fine-grain models, as well as embryonic elements of analysis. The characterization of the algorithm performance is left open, both analytically and experimentally.", 
    "editor": [
      {
        "familyName": "Cicho\u0144", 
        "givenName": "Jacek", 
        "type": "Person"
      }, 
      {
        "familyName": "Ge\u0327bala", 
        "givenName": "Maciej", 
        "type": "Person"
      }, 
      {
        "familyName": "Klonowski", 
        "givenName": "Marek", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39247-4_9", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39246-7", 
        "978-3-642-39247-4"
      ], 
      "name": "Ad-hoc, Mobile, and Wireless Network", 
      "type": "Book"
    }, 
    "name": "Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks", 
    "pagination": "99-110", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39247-4_9"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b747c18a2925cfb8de9b99037e861747099ff54aa391ef818ba01b25690abdc5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038475277"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39247-4_9", 
      "https://app.dimensions.ai/details/publication/pub.1038475277"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T18:12", 
    "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/0000000001_0000000264/records_8681_00000267.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-39247-4_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/978-3-642-39247-4_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/978-3-642-39247-4_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-39247-4_9'

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-642-39247-4_9'


 

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

132 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39247-4_9 schema:about anzsrc-for:07
2 anzsrc-for:0705
3 schema:author Nf3dd6c5992294af4a565a3bc031f0d39
4 schema:citation sg:pub.10.1007/978-3-540-75142-7_10
5 sg:pub.10.1007/s00446-005-0138-3
6 https://doi.org/10.1016/s0743-7315(02)00028-x
7 https://doi.org/10.1109/iceis.2006.1703205
8 https://doi.org/10.1109/mnet.2004.1337732
9 https://doi.org/10.1137/0403039
10 https://doi.org/10.1137/1.9780898719772
11 https://doi.org/10.1145/167088.167256
12 https://doi.org/10.1145/2332432.2332440
13 https://doi.org/10.1145/863955.863960
14 schema:datePublished 2013
15 schema:datePublishedReg 2013-01-01
16 schema:description We address the problem of building and maintaining a forest of spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or existence of a unique root in each fragment regardless of the events, so as to keep these fragments functioning uninterruptedly to a possible extent. Our algorithm operates at a coarse-grain level, using atomic pairwise interactions akin to population protocol or graph relabeling systems. The algorithm relies on a perpetual alternation of topology-induced splittings and computation-induced mergings of a forest of trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk inside the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both merging and splitting are purely localized phenomenons. This paper presents the algorithm and establishes its correctness in arbitrary dynamic networks. We also discuss aspects related to the implementation of this general principle in fine-grain models, as well as embryonic elements of analysis. The characterization of the algorithm performance is left open, both analytically and experimentally.
17 schema:editor Nf90fdc8f9b9f4e0cae55778152c9605d
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf Nbd6065783e2c4ef3a3781be9057a2086
22 schema:name Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks
23 schema:pagination 99-110
24 schema:productId N193fa64262fd470b91e0287a9626e8b1
25 N40741d6aaa1b41258a96e294e587fae9
26 N5d758cd4e087477897d120a2a7e8e608
27 schema:publisher N6b0316a47c254aaabc72c9e1556a766a
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038475277
29 https://doi.org/10.1007/978-3-642-39247-4_9
30 schema:sdDatePublished 2019-04-15T18:12
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Nf3f2937da89b4129b8a689a00d4a1af8
33 schema:url http://link.springer.com/10.1007/978-3-642-39247-4_9
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N02f6e69ce4ff4931baf25a24b64a4821 schema:familyName Cichoń
38 schema:givenName Jacek
39 rdf:type schema:Person
40 N14ad87854e65448ba9f8f0818825deb8 schema:familyName Klonowski
41 schema:givenName Marek
42 rdf:type schema:Person
43 N16dc750e75344093b5ff437d58368e39 rdf:first sg:person.012016610513.97
44 rdf:rest rdf:nil
45 N193fa64262fd470b91e0287a9626e8b1 schema:name dimensions_id
46 schema:value pub.1038475277
47 rdf:type schema:PropertyValue
48 N34747f57f7624074bfff9e26cc6fde07 schema:familyName Gȩbala
49 schema:givenName Maciej
50 rdf:type schema:Person
51 N40741d6aaa1b41258a96e294e587fae9 schema:name doi
52 schema:value 10.1007/978-3-642-39247-4_9
53 rdf:type schema:PropertyValue
54 N51020556dba344ee8790a0922644ca97 rdf:first sg:person.013475656450.23
55 rdf:rest N16dc750e75344093b5ff437d58368e39
56 N5d758cd4e087477897d120a2a7e8e608 schema:name readcube_id
57 schema:value b747c18a2925cfb8de9b99037e861747099ff54aa391ef818ba01b25690abdc5
58 rdf:type schema:PropertyValue
59 N6b0316a47c254aaabc72c9e1556a766a schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 N71693c3da7984e1e8e3094db189d43a2 rdf:first N14ad87854e65448ba9f8f0818825deb8
63 rdf:rest rdf:nil
64 N9d02cdb61d9f4d4e8d439479e457e0c6 schema:name LITIS, University of Le Havre, France
65 rdf:type schema:Organization
66 Nb9aafed6cc1a4226a7c3a424442f3464 schema:name LITIS, University of Le Havre, France
67 rdf:type schema:Organization
68 Nbd6065783e2c4ef3a3781be9057a2086 schema:isbn 978-3-642-39246-7
69 978-3-642-39247-4
70 schema:name Ad-hoc, Mobile, and Wireless Network
71 rdf:type schema:Book
72 Nd73dc125cc894089a2ab3d9d374c3747 rdf:first sg:person.015133652052.91
73 rdf:rest N51020556dba344ee8790a0922644ca97
74 Nd99750de75284b808be2804f31599d5d rdf:first N34747f57f7624074bfff9e26cc6fde07
75 rdf:rest N71693c3da7984e1e8e3094db189d43a2
76 Nf3dd6c5992294af4a565a3bc031f0d39 rdf:first sg:person.014046062661.61
77 rdf:rest Nd73dc125cc894089a2ab3d9d374c3747
78 Nf3f2937da89b4129b8a689a00d4a1af8 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 Nf90fdc8f9b9f4e0cae55778152c9605d rdf:first N02f6e69ce4ff4931baf25a24b64a4821
81 rdf:rest Nd99750de75284b808be2804f31599d5d
82 anzsrc-for:07 schema:inDefinedTermSet anzsrc-for:
83 schema:name Agricultural and Veterinary Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0705 schema:inDefinedTermSet anzsrc-for:
86 schema:name Forestry Sciences
87 rdf:type schema:DefinedTerm
88 sg:person.012016610513.97 schema:affiliation N9d02cdb61d9f4d4e8d439479e457e0c6
89 schema:familyName Pigné
90 schema:givenName Yoann
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012016610513.97
92 rdf:type schema:Person
93 sg:person.013475656450.23 schema:affiliation Nb9aafed6cc1a4226a7c3a424442f3464
94 schema:familyName Guinand
95 schema:givenName Frédéric
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013475656450.23
97 rdf:type schema:Person
98 sg:person.014046062661.61 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
99 schema:familyName Casteigts
100 schema:givenName Arnaud
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61
102 rdf:type schema:Person
103 sg:person.015133652052.91 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
104 schema:familyName Chaumette
105 schema:givenName Serge
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015133652052.91
107 rdf:type schema:Person
108 sg:pub.10.1007/978-3-540-75142-7_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051561882
109 https://doi.org/10.1007/978-3-540-75142-7_10
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s00446-005-0138-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047674948
112 https://doi.org/10.1007/s00446-005-0138-3
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0743-7315(02)00028-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1009725741
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/iceis.2006.1703205 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094587677
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/mnet.2004.1337732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061411423
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/0403039 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844630
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/167088.167256 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034686486
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/2332432.2332440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042858093
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/863955.863960 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018982547
129 rdf:type schema:CreativeWork
130 https://www.grid.ac/institutes/grid.412041.2 schema:alternateName University of Bordeaux
131 schema:name LaBRI, University of Bordeaux, France
132 rdf:type schema:Organization
 




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


...