Multiple Mobile Agent Rendezvous in a Ring View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Paola Flocchini , Evangelos Kranakis , Danny Krizanc , Nicola Santoro , Cindy Sawchuk

ABSTRACT

We study the rendezvous search problem for k ≥ 2 mobile agents in an n node ring. Rather than using randomized algorithms or different deterministic algorithms to break the symmetry that often arises in this problem, we investigate how the mobile agents can use identical stationary tokens to break symmetry and solve the rendezvous problem. After deriving the conditions under which identical stationary tokens can be used to break symmetry, we present several solutions to the rendezvous search problem. We derive the lower bounds of the memory required for mobile agent rendezvous and discuss the relationship between rendezvous and leader election for mobile agents. More... »

PAGES

599-608

References to SciGraph publications

  • 1996. Agent rendezvous: A dynamic symmetry-breaking problem in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Book

    TITLE

    LATIN 2004: Theoretical Informatics

    ISBN

    978-3-540-21258-4
    978-3-540-24698-5

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_62

    DOI

    http://dx.doi.org/10.1007/978-3-540-24698-5_62

    DIMENSIONS

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


    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, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Flocchini", 
            "givenName": "Paola", 
            "id": "sg:person.011601470625.25", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Carleton University", 
              "id": "https://www.grid.ac/institutes/grid.34428.39", 
              "name": [
                "School of Computer Science, Carleton University, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kranakis", 
            "givenName": "Evangelos", 
            "id": "sg:person.01015450242.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01015450242.93"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Wesleyan University", 
              "id": "https://www.grid.ac/institutes/grid.268117.b", 
              "name": [
                "Department of Mathematics and Computer Science, Wesleyan University, 06459, Middletown, Connecticut, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Krizanc", 
            "givenName": "Danny", 
            "id": "sg:person.01200667100.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01200667100.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Carleton University", 
              "id": "https://www.grid.ac/institutes/grid.34428.39", 
              "name": [
                "School of Computer Science, Carleton University, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Santoro", 
            "givenName": "Nicola", 
            "id": "sg:person.010566557723.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Carleton University", 
              "id": "https://www.grid.ac/institutes/grid.34428.39", 
              "name": [
                "School of Computer Science, Carleton University, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sawchuk", 
            "givenName": "Cindy", 
            "id": "sg:person.011252162133.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252162133.94"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-61440-0_163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038487864", 
              "https://doi.org/10.1007/3-540-61440-0_163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/777412.777469", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043112318"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/nav.1044", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051223629"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.45.3.357", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064730955"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.47.6.974", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064731200"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.50.5.772.363", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064731563"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icdcs.2003.1203510", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093976351"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "We study the rendezvous search problem for k \u2265 2 mobile agents in an n node ring. Rather than using randomized algorithms or different deterministic algorithms to break the symmetry that often arises in this problem, we investigate how the mobile agents can use identical stationary tokens to break symmetry and solve the rendezvous problem. After deriving the conditions under which identical stationary tokens can be used to break symmetry, we present several solutions to the rendezvous search problem. We derive the lower bounds of the memory required for mobile agent rendezvous and discuss the relationship between rendezvous and leader election for mobile agents.", 
        "editor": [
          {
            "familyName": "Farach-Colton", 
            "givenName": "Mart\u00edn", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-24698-5_62", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-21258-4", 
            "978-3-540-24698-5"
          ], 
          "name": "LATIN 2004: Theoretical Informatics", 
          "type": "Book"
        }, 
        "name": "Multiple Mobile Agent Rendezvous in a Ring", 
        "pagination": "599-608", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1010697833"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-24698-5_62"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "32f72b3e4c169b07a1a7f37052d585ba9a53c1c5ad24be725e25a1b11ed5d684"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-24698-5_62", 
          "https://app.dimensions.ai/details/publication/pub.1010697833"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:34", 
        "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/0000000365_0000000365/records_71673_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-24698-5_62"
      }
    ]
     

    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-540-24698-5_62'

    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-540-24698-5_62'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_62'

    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-540-24698-5_62'


     

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

    121 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-24698-5_62 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N2bf37ec20f9a4d5ba67e985166fc7731
    4 schema:citation sg:pub.10.1007/3-540-61440-0_163
    5 https://doi.org/10.1002/nav.1044
    6 https://doi.org/10.1109/icdcs.2003.1203510
    7 https://doi.org/10.1145/777412.777469
    8 https://doi.org/10.1287/opre.45.3.357
    9 https://doi.org/10.1287/opre.47.6.974
    10 https://doi.org/10.1287/opre.50.5.772.363
    11 schema:datePublished 2004
    12 schema:datePublishedReg 2004-01-01
    13 schema:description We study the rendezvous search problem for k ≥ 2 mobile agents in an n node ring. Rather than using randomized algorithms or different deterministic algorithms to break the symmetry that often arises in this problem, we investigate how the mobile agents can use identical stationary tokens to break symmetry and solve the rendezvous problem. After deriving the conditions under which identical stationary tokens can be used to break symmetry, we present several solutions to the rendezvous search problem. We derive the lower bounds of the memory required for mobile agent rendezvous and discuss the relationship between rendezvous and leader election for mobile agents.
    14 schema:editor N26f495bb3d94407dada5ce3deea8665c
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N69191ee6eb79455a96ff04d82551e706
    19 schema:name Multiple Mobile Agent Rendezvous in a Ring
    20 schema:pagination 599-608
    21 schema:productId N5afcdb33df6e47cf8793699afd8cb794
    22 Nc652af966d654f6ea9632bb81022fa6e
    23 Nfaa8f52730414e87875ed027ad72f550
    24 schema:publisher N4bcbf8944ff24dc0bbef0c53f7f1b6d0
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010697833
    26 https://doi.org/10.1007/978-3-540-24698-5_62
    27 schema:sdDatePublished 2019-04-16T08:34
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N4a1fc85275184630b8efae78757ed768
    30 schema:url https://link.springer.com/10.1007%2F978-3-540-24698-5_62
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N182a2d6a33eb4c3f9020789e2ac8f742 schema:familyName Farach-Colton
    35 schema:givenName Martín
    36 rdf:type schema:Person
    37 N26f495bb3d94407dada5ce3deea8665c rdf:first N182a2d6a33eb4c3f9020789e2ac8f742
    38 rdf:rest rdf:nil
    39 N2bf37ec20f9a4d5ba67e985166fc7731 rdf:first sg:person.011601470625.25
    40 rdf:rest Nb52e40b27b614158b4625dc84156004f
    41 N4a1fc85275184630b8efae78757ed768 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N4bcbf8944ff24dc0bbef0c53f7f1b6d0 schema:location Berlin, Heidelberg
    44 schema:name Springer Berlin Heidelberg
    45 rdf:type schema:Organisation
    46 N5afcdb33df6e47cf8793699afd8cb794 schema:name readcube_id
    47 schema:value 32f72b3e4c169b07a1a7f37052d585ba9a53c1c5ad24be725e25a1b11ed5d684
    48 rdf:type schema:PropertyValue
    49 N69191ee6eb79455a96ff04d82551e706 schema:isbn 978-3-540-21258-4
    50 978-3-540-24698-5
    51 schema:name LATIN 2004: Theoretical Informatics
    52 rdf:type schema:Book
    53 N80ed4444e7b14fda8665319eb2df7a51 rdf:first sg:person.011252162133.94
    54 rdf:rest rdf:nil
    55 Na380b5f689764044864661e482aaa729 rdf:first sg:person.01200667100.87
    56 rdf:rest Ndb05df8ece424422b4803fc4da1e0b93
    57 Nb52e40b27b614158b4625dc84156004f rdf:first sg:person.01015450242.93
    58 rdf:rest Na380b5f689764044864661e482aaa729
    59 Nc652af966d654f6ea9632bb81022fa6e schema:name dimensions_id
    60 schema:value pub.1010697833
    61 rdf:type schema:PropertyValue
    62 Ndb05df8ece424422b4803fc4da1e0b93 rdf:first sg:person.010566557723.84
    63 rdf:rest N80ed4444e7b14fda8665319eb2df7a51
    64 Nfaa8f52730414e87875ed027ad72f550 schema:name doi
    65 schema:value 10.1007/978-3-540-24698-5_62
    66 rdf:type schema:PropertyValue
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Computation Theory and Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:person.01015450242.93 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    74 schema:familyName Kranakis
    75 schema:givenName Evangelos
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01015450242.93
    77 rdf:type schema:Person
    78 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    79 schema:familyName Santoro
    80 schema:givenName Nicola
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
    82 rdf:type schema:Person
    83 sg:person.011252162133.94 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    84 schema:familyName Sawchuk
    85 schema:givenName Cindy
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252162133.94
    87 rdf:type schema:Person
    88 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    89 schema:familyName Flocchini
    90 schema:givenName Paola
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    92 rdf:type schema:Person
    93 sg:person.01200667100.87 schema:affiliation https://www.grid.ac/institutes/grid.268117.b
    94 schema:familyName Krizanc
    95 schema:givenName Danny
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01200667100.87
    97 rdf:type schema:Person
    98 sg:pub.10.1007/3-540-61440-0_163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038487864
    99 https://doi.org/10.1007/3-540-61440-0_163
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1002/nav.1044 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051223629
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1109/icdcs.2003.1203510 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093976351
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1145/777412.777469 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043112318
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1287/opre.45.3.357 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730955
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1287/opre.47.6.974 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064731200
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1287/opre.50.5.772.363 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064731563
    112 rdf:type schema:CreativeWork
    113 https://www.grid.ac/institutes/grid.268117.b schema:alternateName Wesleyan University
    114 schema:name Department of Mathematics and Computer Science, Wesleyan University, 06459, Middletown, Connecticut, USA
    115 rdf:type schema:Organization
    116 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    117 schema:name SITE, University of Ottawa, Ottawa, ON, Canada
    118 rdf:type schema:Organization
    119 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
    120 schema:name School of Computer Science, Carleton University, Ottawa, ON, Canada
    121 rdf:type schema:Organization
     




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


    ...