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 Nd51f36ce8f9744f98cb35b68a52f770f
    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 N4526ed91aedd4aa7935922fcfe586fff
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf Nca6a9c9611d24ee48ff27a301d95fa39
    19 schema:name Multiple Mobile Agent Rendezvous in a Ring
    20 schema:pagination 599-608
    21 schema:productId N0c908d192f224032be677f98e36c6321
    22 N724d6e0896294acc92f97861dcee0593
    23 Na3f5714b46304a89ac94b94287a35db8
    24 schema:publisher Nc5d37552e3cb47aca28fc307e8308b52
    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 Nc6c3fe45288446b78239dce81f4b39ae
    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 N0c908d192f224032be677f98e36c6321 schema:name readcube_id
    35 schema:value 32f72b3e4c169b07a1a7f37052d585ba9a53c1c5ad24be725e25a1b11ed5d684
    36 rdf:type schema:PropertyValue
    37 N1422517af8b843c4aaa5d3b12a7380b0 rdf:first sg:person.011252162133.94
    38 rdf:rest rdf:nil
    39 N4526ed91aedd4aa7935922fcfe586fff rdf:first N8335037aa47047e28a70c8ec37b50525
    40 rdf:rest rdf:nil
    41 N724d6e0896294acc92f97861dcee0593 schema:name doi
    42 schema:value 10.1007/978-3-540-24698-5_62
    43 rdf:type schema:PropertyValue
    44 N8335037aa47047e28a70c8ec37b50525 schema:familyName Farach-Colton
    45 schema:givenName Martín
    46 rdf:type schema:Person
    47 Na3f5714b46304a89ac94b94287a35db8 schema:name dimensions_id
    48 schema:value pub.1010697833
    49 rdf:type schema:PropertyValue
    50 Na8867e5eb5cb4bdb94b00112b8e14b07 rdf:first sg:person.01015450242.93
    51 rdf:rest Nd343b0b231f94ace90701437d99a214d
    52 Nc5d37552e3cb47aca28fc307e8308b52 schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 Nc6c3fe45288446b78239dce81f4b39ae schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 Nca6a9c9611d24ee48ff27a301d95fa39 schema:isbn 978-3-540-21258-4
    58 978-3-540-24698-5
    59 schema:name LATIN 2004: Theoretical Informatics
    60 rdf:type schema:Book
    61 Nd343b0b231f94ace90701437d99a214d rdf:first sg:person.01200667100.87
    62 rdf:rest Nfb5854d3b09d459b8becdd75fd2e3426
    63 Nd51f36ce8f9744f98cb35b68a52f770f rdf:first sg:person.011601470625.25
    64 rdf:rest Na8867e5eb5cb4bdb94b00112b8e14b07
    65 Nfb5854d3b09d459b8becdd75fd2e3426 rdf:first sg:person.010566557723.84
    66 rdf:rest N1422517af8b843c4aaa5d3b12a7380b0
    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)


    ...