Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Arnaud Casteigts , Serge Chaumette , Afonso Ferreira

ABSTRACT

Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii) the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it. More... »

PAGES

126-140

Book

TITLE

Structural Information and Communication Complexity

ISBN

978-3-642-11475-5
978-3-642-11476-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-11476-2_11

DOI

http://dx.doi.org/10.1007/978-3-642-11476-2_11

DIMENSIONS

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


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": "University of Ottawa", 
          "id": "https://www.grid.ac/institutes/grid.28046.38", 
          "name": [
            "SITE, University of Ottawa, Canada"
          ], 
          "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, Universit\u00e9 de 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": [
            "CNRS - MASCOTTE Project, INRIA Sophia Antipolis, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ferreira", 
        "givenName": "Afonso", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00446-007-0040-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008272694", 
          "https://doi.org/10.1007/s00446-007-0040-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00446-007-0040-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008272694", 
          "https://doi.org/10.1007/s00446-007-0040-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45832-8_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016205410", 
          "https://doi.org/10.1007/3-540-45832-8_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45832-8_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016205410", 
          "https://doi.org/10.1007/3-540-45832-8_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/72981.72982", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016741552"
        ], 
        "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-39611-6_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049147060", 
          "https://doi.org/10.1007/978-3-540-39611-6_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-39611-6_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049147060", 
          "https://doi.org/10.1007/978-3-540-39611-6_23"
        ], 
        "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.1109/tmc.2003.1233531", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061689818"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/9789812814951_0001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088697598"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii) the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it.", 
    "editor": [
      {
        "familyName": "Kutten", 
        "givenName": "Shay", 
        "type": "Person"
      }, 
      {
        "familyName": "\u017derovnik", 
        "givenName": "Janez", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-11476-2_11", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-11475-5", 
        "978-3-642-11476-2"
      ], 
      "name": "Structural Information and Communication Complexity", 
      "type": "Book"
    }, 
    "name": "Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks", 
    "pagination": "126-140", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021306868"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-11476-2_11"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "65843e4ff3182539a4dabe6eee6bf80e7572dbb1e5fa0b87e6c515aff239762b"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-11476-2_11", 
      "https://app.dimensions.ai/details/publication/pub.1021306868"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:32", 
    "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/0000000356_0000000356/records_57898_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-11476-2_11"
  }
]
 

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-11476-2_11'

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-11476-2_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-11476-2_11'

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-11476-2_11'


 

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

116 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-11476-2_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nca95d7a0056547729712690938251dfa
4 schema:citation sg:pub.10.1007/3-540-45832-8_10
5 sg:pub.10.1007/978-3-540-39611-6_23
6 sg:pub.10.1007/s00446-005-0138-3
7 sg:pub.10.1007/s00446-007-0040-2
8 https://doi.org/10.1109/mnet.2004.1337732
9 https://doi.org/10.1109/tmc.2003.1233531
10 https://doi.org/10.1142/9789812814951_0001
11 https://doi.org/10.1145/72981.72982
12 schema:datePublished 2010
13 schema:datePublishedReg 2010-01-01
14 schema:description Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at their assumptions on the underlying network. This paper focuses on the study of such assumptions in dynamic networks, where the connectivity is expected to change, predictably or not, during the execution. Our main contribution is a theoretical framework dedicated to such analysis. By combining several existing components (local computations, graph relabellings, and evolving graphs), this framework allows to express detailed properties on the network dynamics and to prove that a given property is necessary, or sufficient, for the success of an algorithm. Consequences of this work include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) the elaboration of a formal classification of dynamic networks with respect to these properties, and (iii) the possibility to check automatically whether a network trace belongs to one of the classes, and consequently to know which algorithm should run on it.
15 schema:editor Nc81ddfed40f24f04832ab7c4764affe4
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Nc2b0ac88b21447d0874bf824933db741
20 schema:name Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks
21 schema:pagination 126-140
22 schema:productId Na7408fb31e9a4bb5a9e9af5385199237
23 Nb47cb7a390f3477f88ff91c1ccc44831
24 Neb94348ecec94b6cb1ebd11c9a95c10a
25 schema:publisher N3c5fd9e65c2d43109a616ca03a4ee6c6
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021306868
27 https://doi.org/10.1007/978-3-642-11476-2_11
28 schema:sdDatePublished 2019-04-16T07:32
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Na1662bf6911b499f9a8304f0b72a68df
31 schema:url https://link.springer.com/10.1007%2F978-3-642-11476-2_11
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N09da46e45925473a999dc222228248e8 schema:familyName Žerovnik
36 schema:givenName Janez
37 rdf:type schema:Person
38 N0c23671afdfb4831a54d35d8d200e945 rdf:first sg:person.015133652052.91
39 rdf:rest Nea20f11529b241acb9921f117bbfc1dd
40 N304fc743fd7a44ae90fc2c3a83eb11a5 rdf:first N09da46e45925473a999dc222228248e8
41 rdf:rest rdf:nil
42 N3c5fd9e65c2d43109a616ca03a4ee6c6 schema:location Berlin, Heidelberg
43 schema:name Springer Berlin Heidelberg
44 rdf:type schema:Organisation
45 N681bf2f8647143299ac3dacbf70cd939 schema:name CNRS - MASCOTTE Project, INRIA Sophia Antipolis, France
46 rdf:type schema:Organization
47 N9ecdacfcc42f448596438035b5728f0f schema:familyName Kutten
48 schema:givenName Shay
49 rdf:type schema:Person
50 Na1662bf6911b499f9a8304f0b72a68df schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 Na7408fb31e9a4bb5a9e9af5385199237 schema:name doi
53 schema:value 10.1007/978-3-642-11476-2_11
54 rdf:type schema:PropertyValue
55 Nb47cb7a390f3477f88ff91c1ccc44831 schema:name dimensions_id
56 schema:value pub.1021306868
57 rdf:type schema:PropertyValue
58 Nc2b0ac88b21447d0874bf824933db741 schema:isbn 978-3-642-11475-5
59 978-3-642-11476-2
60 schema:name Structural Information and Communication Complexity
61 rdf:type schema:Book
62 Nc81ddfed40f24f04832ab7c4764affe4 rdf:first N9ecdacfcc42f448596438035b5728f0f
63 rdf:rest N304fc743fd7a44ae90fc2c3a83eb11a5
64 Nca95d7a0056547729712690938251dfa rdf:first sg:person.014046062661.61
65 rdf:rest N0c23671afdfb4831a54d35d8d200e945
66 Ncf81e49b29ee4f5bb0860f41331c99f5 schema:affiliation N681bf2f8647143299ac3dacbf70cd939
67 schema:familyName Ferreira
68 schema:givenName Afonso
69 rdf:type schema:Person
70 Nea20f11529b241acb9921f117bbfc1dd rdf:first Ncf81e49b29ee4f5bb0860f41331c99f5
71 rdf:rest rdf:nil
72 Neb94348ecec94b6cb1ebd11c9a95c10a schema:name readcube_id
73 schema:value 65843e4ff3182539a4dabe6eee6bf80e7572dbb1e5fa0b87e6c515aff239762b
74 rdf:type schema:PropertyValue
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.014046062661.61 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
82 schema:familyName Casteigts
83 schema:givenName Arnaud
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014046062661.61
85 rdf:type schema:Person
86 sg:person.015133652052.91 schema:affiliation https://www.grid.ac/institutes/grid.412041.2
87 schema:familyName Chaumette
88 schema:givenName Serge
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015133652052.91
90 rdf:type schema:Person
91 sg:pub.10.1007/3-540-45832-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016205410
92 https://doi.org/10.1007/3-540-45832-8_10
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/978-3-540-39611-6_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049147060
95 https://doi.org/10.1007/978-3-540-39611-6_23
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/s00446-005-0138-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047674948
98 https://doi.org/10.1007/s00446-005-0138-3
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/s00446-007-0040-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008272694
101 https://doi.org/10.1007/s00446-007-0040-2
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1109/mnet.2004.1337732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061411423
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1109/tmc.2003.1233531 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061689818
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1142/9789812814951_0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088697598
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1145/72981.72982 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016741552
110 rdf:type schema:CreativeWork
111 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
112 schema:name SITE, University of Ottawa, Canada
113 rdf:type schema:Organization
114 https://www.grid.ac/institutes/grid.412041.2 schema:alternateName University of Bordeaux
115 schema:name LaBRI, Université de Bordeaux, France
116 rdf:type schema:Organization
 




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


...