Learning a Ring Cheaply and Fast View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Emanuele G. Fusco , Andrzej Pelc , Rossella Petreschi

ABSTRACT

We consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time T we seek bounds on the smallest number of messages needed for learning the ring in time T. Our bounds depend on the diameter D of the ring and on the delay θ = T − D above the least possible time D in which this task can be performed. We prove a lower bound Ω(D 2/θ) on the number of messages used by any algorithm with delay θ, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0 ε θ ≤ D and using O(D 2 (log* D)/θ 1 − ε ) messages. More... »

PAGES

557-568

References to SciGraph publications

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-642-39211-5
978-3-642-39212-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-39212-2_49

DOI

http://dx.doi.org/10.1007/978-3-642-39212-2_49

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Computer Science Department, Sapienza, University of Rome, 00198\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fusco", 
        "givenName": "Emanuele G.", 
        "id": "sg:person.013526501407.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013526501407.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 du Qu\u00e9bec en Outaouais", 
          "id": "https://www.grid.ac/institutes/grid.265705.3", 
          "name": [
            "D\u00e9partement d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Qu\u00e9bec, J8X 3X7, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pelc", 
        "givenName": "Andrzej", 
        "id": "sg:person.013306156242.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "Computer Science Department, Sapienza, University of Rome, 00198\u00a0Rome, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Petreschi", 
        "givenName": "Rossella", 
        "id": "sg:person.011402427702.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/79147.79158", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004122197"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/28395.28421", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005789709"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/359024.359029", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018801160"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(86)80023-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020514024"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/69622.357194", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032495091"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/7531.7919", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033074534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17653-1_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040509143", 
          "https://doi.org/10.1007/978-3-642-17653-1_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-17653-1_10", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040509143", 
          "https://doi.org/10.1007/978-3-642-17653-1_10"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-57811-0_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041243209", 
          "https://doi.org/10.1007/3-540-57811-0_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-006-1212-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042613164", 
          "https://doi.org/10.1007/s00453-006-1212-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/71.481599", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061217493"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0401044", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844533"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0895480295292934", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883187"
        ], 
        "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 consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time T we seek bounds on the smallest number of messages needed for learning the ring in time T. Our bounds depend on the diameter D of the ring and on the delay \u03b8\u2009=\u2009T\u2009\u2212\u2009D above the least possible time D in which this task can be performed. We prove a lower bound \u03a9(D 2/\u03b8) on the number of messages used by any algorithm with delay \u03b8, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0\u2009\u03b5\u2009\u03b8\u2009\u2264\u2009D and using O(D 2 (log* D)/\u03b8 1\u2009\u2212\u2009\u03b5 ) messages.", 
    "editor": [
      {
        "familyName": "Fomin", 
        "givenName": "Fedor V.", 
        "type": "Person"
      }, 
      {
        "familyName": "Freivalds", 
        "givenName": "R\u016bsi\u0146\u0161", 
        "type": "Person"
      }, 
      {
        "familyName": "Kwiatkowska", 
        "givenName": "Marta", 
        "type": "Person"
      }, 
      {
        "familyName": "Peleg", 
        "givenName": "David", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-39212-2_49", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-39211-5", 
        "978-3-642-39212-2"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "name": "Learning a Ring Cheaply and Fast", 
    "pagination": "557-568", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-39212-2_49"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8f0692e86873677204da105f5c367078a6f92b848c735bdb0e0ff0a58a5599ad"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1030022595"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-39212-2_49", 
      "https://app.dimensions.ai/details/publication/pub.1030022595"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:52", 
    "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_8697_00000261.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-39212-2_49"
  }
]
 

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-39212-2_49'

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-39212-2_49'

Turtle is a human-readable linked data format.

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

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-39212-2_49'


 

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

139 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-39212-2_49 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N68cfc02cd8c14b769faf6e4b53dd8ff1
4 schema:citation sg:pub.10.1007/3-540-57811-0_14
5 sg:pub.10.1007/978-3-642-17653-1_10
6 sg:pub.10.1007/s00453-006-1212-3
7 https://doi.org/10.1016/s0019-9958(86)80023-7
8 https://doi.org/10.1109/71.481599
9 https://doi.org/10.1137/0401044
10 https://doi.org/10.1137/1.9780898719772
11 https://doi.org/10.1137/s0895480295292934
12 https://doi.org/10.1145/28395.28421
13 https://doi.org/10.1145/359024.359029
14 https://doi.org/10.1145/69622.357194
15 https://doi.org/10.1145/7531.7919
16 https://doi.org/10.1145/79147.79158
17 schema:datePublished 2013
18 schema:datePublishedReg 2013-01-01
19 schema:description We consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time T we seek bounds on the smallest number of messages needed for learning the ring in time T. Our bounds depend on the diameter D of the ring and on the delay θ = T − D above the least possible time D in which this task can be performed. We prove a lower bound Ω(D 2/θ) on the number of messages used by any algorithm with delay θ, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0 ε θ ≤ D and using O(D 2 (log* D)/θ 1 − ε ) messages.
20 schema:editor N97d6f9a2f80944268aed130bb15af747
21 schema:genre chapter
22 schema:inLanguage en
23 schema:isAccessibleForFree true
24 schema:isPartOf N97ebfc81a27442b38bcbe7ddda104694
25 schema:name Learning a Ring Cheaply and Fast
26 schema:pagination 557-568
27 schema:productId N055e9cf926864d6fbb3c45a99d2f1a26
28 N17d495222691420ea0b808c0189d489e
29 N393118eb03bb45dcb6fbe7ec9e4b0eba
30 schema:publisher N33f9b5da6da941f7aca74bee336e389d
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030022595
32 https://doi.org/10.1007/978-3-642-39212-2_49
33 schema:sdDatePublished 2019-04-15T23:52
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nfd7a4f9db58a4e65ac8cf7989ff97790
36 schema:url http://link.springer.com/10.1007/978-3-642-39212-2_49
37 sgo:license sg:explorer/license/
38 sgo:sdDataset chapters
39 rdf:type schema:Chapter
40 N055e9cf926864d6fbb3c45a99d2f1a26 schema:name doi
41 schema:value 10.1007/978-3-642-39212-2_49
42 rdf:type schema:PropertyValue
43 N17d495222691420ea0b808c0189d489e schema:name dimensions_id
44 schema:value pub.1030022595
45 rdf:type schema:PropertyValue
46 N2fd2e73dfc66468cbbc03cf92a24e9ec schema:familyName Peleg
47 schema:givenName David
48 rdf:type schema:Person
49 N33f9b5da6da941f7aca74bee336e389d schema:location Berlin, Heidelberg
50 schema:name Springer Berlin Heidelberg
51 rdf:type schema:Organisation
52 N393118eb03bb45dcb6fbe7ec9e4b0eba schema:name readcube_id
53 schema:value 8f0692e86873677204da105f5c367078a6f92b848c735bdb0e0ff0a58a5599ad
54 rdf:type schema:PropertyValue
55 N4c0deec3aef14167b2ff29c303ed4549 rdf:first sg:person.011402427702.78
56 rdf:rest rdf:nil
57 N68cfc02cd8c14b769faf6e4b53dd8ff1 rdf:first sg:person.013526501407.57
58 rdf:rest Nd48a9068531e4e19ab93d1cc74619a5c
59 N781d89628ff74a2c9fd24c5921abcd4a schema:familyName Kwiatkowska
60 schema:givenName Marta
61 rdf:type schema:Person
62 N7dd5b98997244ec593ae1a9dce44540a rdf:first N781d89628ff74a2c9fd24c5921abcd4a
63 rdf:rest N89cfb993804f43408dbd5b9a7e708dc9
64 N8503801e7678441dbae3288ac3b97ad5 schema:familyName Fomin
65 schema:givenName Fedor V.
66 rdf:type schema:Person
67 N89cfb993804f43408dbd5b9a7e708dc9 rdf:first N2fd2e73dfc66468cbbc03cf92a24e9ec
68 rdf:rest rdf:nil
69 N97d6f9a2f80944268aed130bb15af747 rdf:first N8503801e7678441dbae3288ac3b97ad5
70 rdf:rest Nbb3559b075154c87ba962535f156374b
71 N97ebfc81a27442b38bcbe7ddda104694 schema:isbn 978-3-642-39211-5
72 978-3-642-39212-2
73 schema:name Automata, Languages, and Programming
74 rdf:type schema:Book
75 Nbb3559b075154c87ba962535f156374b rdf:first Nfc4549b90daf4bd1986d367c5be2ba73
76 rdf:rest N7dd5b98997244ec593ae1a9dce44540a
77 Nd48a9068531e4e19ab93d1cc74619a5c rdf:first sg:person.013306156242.32
78 rdf:rest N4c0deec3aef14167b2ff29c303ed4549
79 Nfc4549b90daf4bd1986d367c5be2ba73 schema:familyName Freivalds
80 schema:givenName Rūsiņš
81 rdf:type schema:Person
82 Nfd7a4f9db58a4e65ac8cf7989ff97790 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
85 schema:name Information and Computing Sciences
86 rdf:type schema:DefinedTerm
87 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
88 schema:name Artificial Intelligence and Image Processing
89 rdf:type schema:DefinedTerm
90 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
91 schema:familyName Petreschi
92 schema:givenName Rossella
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
94 rdf:type schema:Person
95 sg:person.013306156242.32 schema:affiliation https://www.grid.ac/institutes/grid.265705.3
96 schema:familyName Pelc
97 schema:givenName Andrzej
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013306156242.32
99 rdf:type schema:Person
100 sg:person.013526501407.57 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
101 schema:familyName Fusco
102 schema:givenName Emanuele G.
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013526501407.57
104 rdf:type schema:Person
105 sg:pub.10.1007/3-540-57811-0_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041243209
106 https://doi.org/10.1007/3-540-57811-0_14
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-3-642-17653-1_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040509143
109 https://doi.org/10.1007/978-3-642-17653-1_10
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s00453-006-1212-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042613164
112 https://doi.org/10.1007/s00453-006-1212-3
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/s0019-9958(86)80023-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020514024
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/71.481599 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217493
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1137/0401044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844533
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/s0895480295292934 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883187
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/28395.28421 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005789709
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/359024.359029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018801160
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/69622.357194 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032495091
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/7531.7919 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033074534
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/79147.79158 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004122197
133 rdf:type schema:CreativeWork
134 https://www.grid.ac/institutes/grid.265705.3 schema:alternateName Université du Québec en Outaouais
135 schema:name Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec, J8X 3X7, Canada
136 rdf:type schema:Organization
137 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
138 schema:name Computer Science Department, Sapienza, University of Rome, 00198 Rome, Italy
139 rdf:type schema:Organization
 




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


...