Agent rendezvous: A dynamic symmetry-breaking problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1996

AUTHORS

Xiangdong Yu , Moti Yung

ABSTRACT

We consider the problem of a rendezvous (coordinated meeting) of distributed units (intelligent agents in network computing or autonomous robots). The environment is modeled as a graph, the node labeling of which may not be “common knowledge” to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility of the environment. Meeting of such units is likely to be a basic procedure in the area of distributed “intelligent agent” computing and in the domain of coordinated tasks of autonomous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent (computing power, control and memory) than simple (traditional) pebbles or tokens, and our algorithms will make use of this capability for speeding up the convergence to a common place (e.g., we will allow units to meet exchange information and depart). We consider both randomized protocols and deterministic (but non-uniform) protocols; the problem is unsolvable by a uniform deterministic algorithm. The deterministic procedure employs ideas from design theory and achieves Õ(n) time, while the randomized methods are based on random walks and may achieve Õ(n) time where k is the number of agents. More... »

PAGES

610-621

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-61440-1
978-3-540-68580-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-61440-0_163

DOI

http://dx.doi.org/10.1007/3-540-61440-0_163

DIMENSIONS

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


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": "Columbia University", 
          "id": "https://www.grid.ac/institutes/grid.21729.3f", 
          "name": [
            "Computer Science Department, Columbia University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yu", 
        "givenName": "Xiangdong", 
        "id": "sg:person.016306310142.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016306310142.08"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Research Division, T.J. Watson Center, 10598\u00a0Yorktown Heights, NY"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yung", 
        "givenName": "Moti", 
        "id": "sg:person.016677435253.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016677435253.49"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0304-3975(91)90263-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050621281"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996", 
    "datePublishedReg": "1996-01-01", 
    "description": "We consider the problem of a rendezvous (coordinated meeting) of distributed units (intelligent agents in network computing or autonomous robots). The environment is modeled as a graph, the node labeling of which may not be \u201ccommon knowledge\u201d to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility of the environment. Meeting of such units is likely to be a basic procedure in the area of distributed \u201cintelligent agent\u201d computing and in the domain of coordinated tasks of autonomous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent (computing power, control and memory) than simple (traditional) pebbles or tokens, and our algorithms will make use of this capability for speeding up the convergence to a common place (e.g., we will allow units to meet exchange information and depart). We consider both randomized protocols and deterministic (but non-uniform) protocols; the problem is unsolvable by a uniform deterministic algorithm. The deterministic procedure employs ideas from design theory and achieves \u00d5(n) time, while the randomized methods are based on random walks and may achieve \u00d5(n) time where k is the number of agents.", 
    "editor": [
      {
        "familyName": "Meyer", 
        "givenName": "Friedhelm", 
        "type": "Person"
      }, 
      {
        "familyName": "Monien", 
        "givenName": "Burkhard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-61440-0_163", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3388542", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3417312", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": {
      "isbn": [
        "978-3-540-61440-1", 
        "978-3-540-68580-7"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "Agent rendezvous: A dynamic symmetry-breaking problem", 
    "pagination": "610-621", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-61440-0_163"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b756e0cbf449555b550e7a295b59dbeae9a6a4198f9e348aae9efec2139f1d53"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038487864"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-61440-0_163", 
      "https://app.dimensions.ai/details/publication/pub.1038487864"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:03", 
    "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_8690_00000267.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-61440-0_163"
  }
]
 

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/3-540-61440-0_163'

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/3-540-61440-0_163'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-61440-0_163'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-61440-0_163'


 

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

87 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-61440-0_163 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N4cb696b5951e4f20b11b2a63b9f66650
4 schema:citation https://doi.org/10.1016/0304-3975(91)90263-2
5 schema:datePublished 1996
6 schema:datePublishedReg 1996-01-01
7 schema:description We consider the problem of a rendezvous (coordinated meeting) of distributed units (intelligent agents in network computing or autonomous robots). The environment is modeled as a graph, the node labeling of which may not be “common knowledge” to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility of the environment. Meeting of such units is likely to be a basic procedure in the area of distributed “intelligent agent” computing and in the domain of coordinated tasks of autonomous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent (computing power, control and memory) than simple (traditional) pebbles or tokens, and our algorithms will make use of this capability for speeding up the convergence to a common place (e.g., we will allow units to meet exchange information and depart). We consider both randomized protocols and deterministic (but non-uniform) protocols; the problem is unsolvable by a uniform deterministic algorithm. The deterministic procedure employs ideas from design theory and achieves Õ(n) time, while the randomized methods are based on random walks and may achieve Õ(n) time where k is the number of agents.
8 schema:editor N2b05fec3eb144499854aa2e7a167bc91
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Nb26dcccfa8be42b88f265e386646a526
13 schema:name Agent rendezvous: A dynamic symmetry-breaking problem
14 schema:pagination 610-621
15 schema:productId N067313d11487449a97393ad02d27f281
16 N3695a1d0cd7f4401b89b4ee74f0810a6
17 Ne6e92f44de2244a198c0bdbc3436ab9b
18 schema:publisher N91dfc9949c7641e1af3c17029df90283
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038487864
20 https://doi.org/10.1007/3-540-61440-0_163
21 schema:sdDatePublished 2019-04-15T21:03
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher Ne723f1a9794a4a028d50f1753d456aef
24 schema:url http://link.springer.com/10.1007/3-540-61440-0_163
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N067313d11487449a97393ad02d27f281 schema:name dimensions_id
29 schema:value pub.1038487864
30 rdf:type schema:PropertyValue
31 N2b05fec3eb144499854aa2e7a167bc91 rdf:first N9d70673a9f3842ca9c878ac6df63b6ac
32 rdf:rest N677f1a4f152e4c13a366207d2ebf1c1d
33 N3695a1d0cd7f4401b89b4ee74f0810a6 schema:name readcube_id
34 schema:value b756e0cbf449555b550e7a295b59dbeae9a6a4198f9e348aae9efec2139f1d53
35 rdf:type schema:PropertyValue
36 N4cb696b5951e4f20b11b2a63b9f66650 rdf:first sg:person.016306310142.08
37 rdf:rest N946fba17824c49fabfb7acc696e731e8
38 N5c3abd16ae5b4091b390e035dde264b7 schema:familyName Monien
39 schema:givenName Burkhard
40 rdf:type schema:Person
41 N677f1a4f152e4c13a366207d2ebf1c1d rdf:first N5c3abd16ae5b4091b390e035dde264b7
42 rdf:rest rdf:nil
43 N91dfc9949c7641e1af3c17029df90283 schema:location Berlin, Heidelberg
44 schema:name Springer Berlin Heidelberg
45 rdf:type schema:Organisation
46 N946fba17824c49fabfb7acc696e731e8 rdf:first sg:person.016677435253.49
47 rdf:rest rdf:nil
48 N9d70673a9f3842ca9c878ac6df63b6ac schema:familyName Meyer
49 schema:givenName Friedhelm
50 rdf:type schema:Person
51 Nb26dcccfa8be42b88f265e386646a526 schema:isbn 978-3-540-61440-1
52 978-3-540-68580-7
53 schema:name Automata, Languages and Programming
54 rdf:type schema:Book
55 Ne6e92f44de2244a198c0bdbc3436ab9b schema:name doi
56 schema:value 10.1007/3-540-61440-0_163
57 rdf:type schema:PropertyValue
58 Ne723f1a9794a4a028d50f1753d456aef schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
64 schema:name Artificial Intelligence and Image Processing
65 rdf:type schema:DefinedTerm
66 sg:grant.3388542 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-61440-0_163
67 rdf:type schema:MonetaryGrant
68 sg:grant.3417312 http://pending.schema.org/fundedItem sg:pub.10.1007/3-540-61440-0_163
69 rdf:type schema:MonetaryGrant
70 sg:person.016306310142.08 schema:affiliation https://www.grid.ac/institutes/grid.21729.3f
71 schema:familyName Yu
72 schema:givenName Xiangdong
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016306310142.08
74 rdf:type schema:Person
75 sg:person.016677435253.49 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
76 schema:familyName Yung
77 schema:givenName Moti
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016677435253.49
79 rdf:type schema:Person
80 https://doi.org/10.1016/0304-3975(91)90263-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050621281
81 rdf:type schema:CreativeWork
82 https://www.grid.ac/institutes/grid.21729.3f schema:alternateName Columbia University
83 schema:name Computer Science Department, Columbia University, USA
84 rdf:type schema:Organization
85 https://www.grid.ac/institutes/grid.481554.9 schema:alternateName IBM Research – Thomas J. Watson Research Center
86 schema:name IBM Research Division, T.J. Watson Center, 10598 Yorktown Heights, NY
87 rdf:type schema:Organization
 




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


...