Local MST Computation with Short Advice View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-11

AUTHORS

Pierre Fraigniaud, Amos Korman, Emmanuelle Lebhar

ABSTRACT

We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ℘ is a way, for every possible input I of ℘, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ℘ can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (⌈log n⌉,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies . Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log n to constant. More... »

PAGES

920-933

References to SciGraph publications

  • 2005. Label-Guided Graph Exploration by a Finite Automaton in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2005. Labeling Schemes for Tree Representation in DISTRIBUTED COMPUTING – IWDC 2005
  • 2006. Tree Exploration with an Oracle in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-010-9280-9

    DOI

    http://dx.doi.org/10.1007/s00224-010-9280-9

    DIMENSIONS

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


    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": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Univ. Paris 7, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fraigniaud", 
            "givenName": "Pierre", 
            "id": "sg:person.013424402135.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Univ. Paris 7, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Korman", 
            "givenName": "Amos", 
            "id": "sg:person.013353220506.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Paris Diderot University", 
              "id": "https://www.grid.ac/institutes/grid.7452.4", 
              "name": [
                "CNRS and Univ. Paris 7, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lebhar", 
            "givenName": "Emmanuelle", 
            "id": "sg:person.013001553446.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013001553446.73"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/1146381.1146410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005207210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603771_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014679656", 
              "https://doi.org/10.1007/11603771_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11603771_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014679656", 
              "https://doi.org/10.1007/11603771_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/383962.383984", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027854661"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/357195.357200", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032636611"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037978405", 
              "https://doi.org/10.1007/11821069_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11821069_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037978405", 
              "https://doi.org/10.1007/11821069_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777412.777428", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040783541"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/323596.323612", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042764094"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1146381.1146389", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043358496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1073814.1073817", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049189391"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/167088.167149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051815222"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0221015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842347"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sffcs.1999.814597", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095520179"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898719772", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557268"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-11", 
        "datePublishedReg": "2010-11-01", 
        "description": "We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem \u2118 is a way, for every possible input I of \u2118, to provide an \u201cadvice\u201d (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem \u2118 can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (\u2308log n\u2309,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies . Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size \u03a9(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log n to constant.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00224-010-9280-9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "47"
          }
        ], 
        "name": "Local MST Computation with Short Advice", 
        "pagination": "920-933", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a84867b5e8218b0a812555df762af9e2b87027972380eca179e2b061bf67d6d2"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-010-9280-9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035327269"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-010-9280-9", 
          "https://app.dimensions.ai/details/publication/pub.1035327269"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T23:19", 
        "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_8693_00000489.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00224-010-9280-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/s00224-010-9280-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/s00224-010-9280-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9280-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-010-9280-9'


     

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

    120 TRIPLES      21 PREDICATES      41 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-010-9280-9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6c8be54dfd8646ed93ddec6862a928a3
    4 schema:citation sg:pub.10.1007/11523468_28
    5 sg:pub.10.1007/11603771_2
    6 sg:pub.10.1007/11821069_2
    7 https://doi.org/10.1109/sffcs.1999.814597
    8 https://doi.org/10.1137/0221015
    9 https://doi.org/10.1137/1.9780898719772
    10 https://doi.org/10.1145/1073814.1073817
    11 https://doi.org/10.1145/1146381.1146389
    12 https://doi.org/10.1145/1146381.1146410
    13 https://doi.org/10.1145/167088.167149
    14 https://doi.org/10.1145/323596.323612
    15 https://doi.org/10.1145/357195.357200
    16 https://doi.org/10.1145/383962.383984
    17 https://doi.org/10.1145/777412.777428
    18 schema:datePublished 2010-11
    19 schema:datePublishedReg 2010-11-01
    20 schema:description We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ℘ is a way, for every possible input I of ℘, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ℘ can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (⌈log n⌉,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies . Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log n to constant.
    21 schema:genre research_article
    22 schema:inLanguage en
    23 schema:isAccessibleForFree true
    24 schema:isPartOf N18bcbcb834814bf2ae620efdec58406c
    25 N850f70a0abcd40049925e2f06bcaf3ea
    26 sg:journal.1052098
    27 schema:name Local MST Computation with Short Advice
    28 schema:pagination 920-933
    29 schema:productId N2e52109bcfb941069677154faba82659
    30 N9458a72efd1e432baa41d26ddedaba9e
    31 Nc087ec62d68a4f5aa4722ba147909908
    32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035327269
    33 https://doi.org/10.1007/s00224-010-9280-9
    34 schema:sdDatePublished 2019-04-10T23:19
    35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    36 schema:sdPublisher N0d1147ac3b754b508c02eb51fa46e1c0
    37 schema:url http://link.springer.com/10.1007/s00224-010-9280-9
    38 sgo:license sg:explorer/license/
    39 sgo:sdDataset articles
    40 rdf:type schema:ScholarlyArticle
    41 N08670950317d456788a0303fbbd40897 rdf:first sg:person.013001553446.73
    42 rdf:rest rdf:nil
    43 N0d1147ac3b754b508c02eb51fa46e1c0 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N18bcbcb834814bf2ae620efdec58406c schema:volumeNumber 47
    46 rdf:type schema:PublicationVolume
    47 N1b04fb5f0b464391823081726af02708 rdf:first sg:person.013353220506.00
    48 rdf:rest N08670950317d456788a0303fbbd40897
    49 N2e52109bcfb941069677154faba82659 schema:name readcube_id
    50 schema:value a84867b5e8218b0a812555df762af9e2b87027972380eca179e2b061bf67d6d2
    51 rdf:type schema:PropertyValue
    52 N6c8be54dfd8646ed93ddec6862a928a3 rdf:first sg:person.013424402135.28
    53 rdf:rest N1b04fb5f0b464391823081726af02708
    54 N850f70a0abcd40049925e2f06bcaf3ea schema:issueNumber 4
    55 rdf:type schema:PublicationIssue
    56 N9458a72efd1e432baa41d26ddedaba9e schema:name dimensions_id
    57 schema:value pub.1035327269
    58 rdf:type schema:PropertyValue
    59 Nc087ec62d68a4f5aa4722ba147909908 schema:name doi
    60 schema:value 10.1007/s00224-010-9280-9
    61 rdf:type schema:PropertyValue
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Computation Theory and Mathematics
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1052098 schema:issn 1432-4350
    69 1433-0490
    70 schema:name Theory of Computing Systems
    71 rdf:type schema:Periodical
    72 sg:person.013001553446.73 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    73 schema:familyName Lebhar
    74 schema:givenName Emmanuelle
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013001553446.73
    76 rdf:type schema:Person
    77 sg:person.013353220506.00 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    78 schema:familyName Korman
    79 schema:givenName Amos
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00
    81 rdf:type schema:Person
    82 sg:person.013424402135.28 schema:affiliation https://www.grid.ac/institutes/grid.7452.4
    83 schema:familyName Fraigniaud
    84 schema:givenName Pierre
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
    86 rdf:type schema:Person
    87 sg:pub.10.1007/11523468_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040407045
    88 https://doi.org/10.1007/11523468_28
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/11603771_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014679656
    91 https://doi.org/10.1007/11603771_2
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/11821069_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037978405
    94 https://doi.org/10.1007/11821069_2
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1109/sffcs.1999.814597 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095520179
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1137/0221015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842347
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1145/1073814.1073817 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049189391
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1145/1146381.1146389 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043358496
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1145/1146381.1146410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005207210
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/167088.167149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051815222
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/323596.323612 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042764094
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/357195.357200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032636611
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/383962.383984 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027854661
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1145/777412.777428 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040783541
    117 rdf:type schema:CreativeWork
    118 https://www.grid.ac/institutes/grid.7452.4 schema:alternateName Paris Diderot University
    119 schema:name CNRS and Univ. Paris 7, Paris, France
    120 rdf:type schema:Organization
     




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


    ...