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 N841a69f379bc490e9ca7ba28adc8ef24
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 N9ced4aecb181425a950a054bb360fb97
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N6daab1023df4411a8d85e9419d7320a5
13 schema:name Agent rendezvous: A dynamic symmetry-breaking problem
14 schema:pagination 610-621
15 schema:productId N24588ace9d1746bbb3d7f296101edb3a
16 N5524c95eff6f4e65a37a76405e5c6dbe
17 N8f8daf3ab2194d5784800b1c0df9f92b
18 schema:publisher Nc9afe99c88594662a5fd95d3da333a18
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 Ne8454d0f01144c778f7f581420a0cb54
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 N24588ace9d1746bbb3d7f296101edb3a schema:name readcube_id
29 schema:value b756e0cbf449555b550e7a295b59dbeae9a6a4198f9e348aae9efec2139f1d53
30 rdf:type schema:PropertyValue
31 N3f8edadee1304a3ba57519de92b6a617 schema:familyName Monien
32 schema:givenName Burkhard
33 rdf:type schema:Person
34 N45510170826c4db58f05a14b7c9381bd schema:familyName Meyer
35 schema:givenName Friedhelm
36 rdf:type schema:Person
37 N54a02fd8533d41d8a95cb1d715518c91 rdf:first sg:person.016677435253.49
38 rdf:rest rdf:nil
39 N5524c95eff6f4e65a37a76405e5c6dbe schema:name dimensions_id
40 schema:value pub.1038487864
41 rdf:type schema:PropertyValue
42 N60a5bfb2c5bf451da669e5d446a8cc6e rdf:first N3f8edadee1304a3ba57519de92b6a617
43 rdf:rest rdf:nil
44 N6daab1023df4411a8d85e9419d7320a5 schema:isbn 978-3-540-61440-1
45 978-3-540-68580-7
46 schema:name Automata, Languages and Programming
47 rdf:type schema:Book
48 N841a69f379bc490e9ca7ba28adc8ef24 rdf:first sg:person.016306310142.08
49 rdf:rest N54a02fd8533d41d8a95cb1d715518c91
50 N8f8daf3ab2194d5784800b1c0df9f92b schema:name doi
51 schema:value 10.1007/3-540-61440-0_163
52 rdf:type schema:PropertyValue
53 N9ced4aecb181425a950a054bb360fb97 rdf:first N45510170826c4db58f05a14b7c9381bd
54 rdf:rest N60a5bfb2c5bf451da669e5d446a8cc6e
55 Nc9afe99c88594662a5fd95d3da333a18 schema:location Berlin, Heidelberg
56 schema:name Springer Berlin Heidelberg
57 rdf:type schema:Organisation
58 Ne8454d0f01144c778f7f581420a0cb54 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)


...