Distributed exploration of dynamic rings View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-08-20

AUTHORS

G. Di Luna, S. Dobrev, P. Flocchini, N. Santoro

ABSTRACT

In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal. More... »

PAGES

1-27

References to SciGraph publications

  • 2012-01. Searching for Black Holes in Subways in THEORY OF COMPUTING SYSTEMS
  • 2011. On the Power of Waiting When Exploring Public Transportation Systems in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2012. Agreement in Directed Dynamic Networks in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2013. Eventual Leader Election in Evolving Mobile Networks in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2008. How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2015. Computing the Dynamic Diameter of Non-Deterministic Dynamic Networks is Hard in ALGORITHMS FOR SENSOR SYSTEMS
  • 2015. On Temporal Graph Exploration in AUTOMATA, LANGUAGES, AND PROGRAMMING
  • 2014. Conscious and Unconscious Counting on Anonymous Dynamic Networks in DISTRIBUTED COMPUTING AND NETWORKING
  • 2006. Searching for Black-Hole Faults in a Network Using Multiple Agents in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2013. Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2011-09. Parsimonious flooding in dynamic graphs in DISTRIBUTED COMPUTING
  • 2006-09. Searching for a black hole in arbitrary networks: optimal mobile agents protocols in DISTRIBUTED COMPUTING
  • 2014. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00446-018-0339-1

    DOI

    http://dx.doi.org/10.1007/s00446-018-0339-1

    DIMENSIONS

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


    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": [
                "School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Di Luna", 
            "givenName": "G.", 
            "id": "sg:person.015542601431.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015542601431.41"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Slovak Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.419303.c", 
              "name": [
                "Slovak Academy of Sciences, D\u00fabravsk\u00e1 cesta 9, 811 04, Bratislava, Slovakia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dobrev", 
            "givenName": "S.", 
            "id": "sg:person.0610371471.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Ottawa", 
              "id": "https://www.grid.ac/institutes/grid.28046.38", 
              "name": [
                "School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Flocchini", 
            "givenName": "P.", 
            "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, 1125 Colonel By Drive, Ottawa, ON, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Santoro", 
            "givenName": "N.", 
            "id": "sg:person.010566557723.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s00446-006-0154-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000916693", 
              "https://doi.org/10.1007/s00446-006-0154-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-006-0154-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000916693", 
              "https://doi.org/10.1007/s00446-006-0154-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00224-011-9341-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004728379", 
              "https://doi.org/10.1007/s00224-011-9341-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2016.04.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005155299"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/17445760.2012.668546", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005693413"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2005.07.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006352716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2005.07.014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006352716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2012.11.022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006374898"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2014.07.013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008752835"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010742782"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-46018-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011019112", 
              "https://doi.org/10.1007/978-3-662-46018-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2012.10.029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012732800"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1999.1043", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014281330"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/800222.806754", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018316918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2767386.2767442", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018608128"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2007.05.011", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022545213"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70575-8_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027002019", 
              "https://doi.org/10.1007/978-3-540-70575-8_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-03578-9_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027423063", 
              "https://doi.org/10.1007/978-3-319-03578-9_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2008.02.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028600334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2484239.2484275", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030991275"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00446-011-0133-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031581381", 
              "https://doi.org/10.1007/s00446-011-0133-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-09620-9_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031791144", 
              "https://doi.org/10.1007/978-3-319-09620-9_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2013.01.025", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033715963"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-03850-6_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035063247", 
              "https://doi.org/10.1007/978-3-319-03850-6_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2594581", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035640119"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1993806.1993808", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036726748"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-45249-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041512596", 
              "https://doi.org/10.1007/978-3-642-45249-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0895-7177(97)00050-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041577640"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-31104-8_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045024105", 
              "https://doi.org/10.1007/978-3-642-31104-8_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-47672-7_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046778621", 
              "https://doi.org/10.1007/978-3-662-47672-7_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1806689.1806760", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046808496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047952182", 
              "https://doi.org/10.1007/11945529_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11945529_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047952182", 
              "https://doi.org/10.1007/11945529_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-25873-2_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051713335", 
              "https://doi.org/10.1007/978-3-642-25873-2_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/mnet.2004.1337732", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061411423"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.2012.208", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061535334"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2008.218", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753328"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tpds.2011.33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061753875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753979732428x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880193"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054103001728", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062896465"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129054115500288", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062897477"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipdps.2009.5161080", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093705627"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-08-20", 
        "datePublishedReg": "2018-08-20", 
        "description": "In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00446-018-0339-1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052621", 
            "issn": [
              "0178-2770", 
              "1432-0452"
            ], 
            "name": "Distributed Computing", 
            "type": "Periodical"
          }
        ], 
        "name": "Distributed exploration of dynamic rings", 
        "pagination": "1-27", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "65607d220d187190193961e119798717a945c146b03e31b0553888cec9f16784"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00446-018-0339-1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1106255147"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00446-018-0339-1", 
          "https://app.dimensions.ai/details/publication/pub.1106255147"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T14:05", 
        "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_8660_00000494.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00446-018-0339-1"
      }
    ]
     

    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/s00446-018-0339-1'

    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/s00446-018-0339-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00446-018-0339-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00446-018-0339-1'


     

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

    212 TRIPLES      21 PREDICATES      63 URIs      16 LITERALS      5 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00446-018-0339-1 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N76b356b2d76f408e82f1437f73d4f733
    4 schema:citation sg:pub.10.1007/11945529_23
    5 sg:pub.10.1007/978-3-319-03578-9_2
    6 sg:pub.10.1007/978-3-319-03850-6_3
    7 sg:pub.10.1007/978-3-319-09620-9_20
    8 sg:pub.10.1007/978-3-540-70575-8_11
    9 sg:pub.10.1007/978-3-642-25873-2_31
    10 sg:pub.10.1007/978-3-642-31104-8_7
    11 sg:pub.10.1007/978-3-642-45249-9_17
    12 sg:pub.10.1007/978-3-662-46018-4_6
    13 sg:pub.10.1007/978-3-662-47672-7_36
    14 sg:pub.10.1007/s00224-011-9341-8
    15 sg:pub.10.1007/s00446-006-0154-y
    16 sg:pub.10.1007/s00446-011-0133-9
    17 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8
    18 https://doi.org/10.1006/jagm.1999.1043
    19 https://doi.org/10.1016/j.tcs.2005.07.014
    20 https://doi.org/10.1016/j.tcs.2007.05.011
    21 https://doi.org/10.1016/j.tcs.2008.02.006
    22 https://doi.org/10.1016/j.tcs.2012.10.029
    23 https://doi.org/10.1016/j.tcs.2012.11.022
    24 https://doi.org/10.1016/j.tcs.2013.01.025
    25 https://doi.org/10.1016/j.tcs.2014.07.013
    26 https://doi.org/10.1016/j.tcs.2016.04.006
    27 https://doi.org/10.1016/s0895-7177(97)00050-2
    28 https://doi.org/10.1080/17445760.2012.668546
    29 https://doi.org/10.1109/ipdps.2009.5161080
    30 https://doi.org/10.1109/mnet.2004.1337732
    31 https://doi.org/10.1109/tc.2012.208
    32 https://doi.org/10.1109/tpds.2008.218
    33 https://doi.org/10.1109/tpds.2011.33
    34 https://doi.org/10.1137/s009753979732428x
    35 https://doi.org/10.1142/s0129054103001728
    36 https://doi.org/10.1142/s0129054115500288
    37 https://doi.org/10.1145/1806689.1806760
    38 https://doi.org/10.1145/1993806.1993808
    39 https://doi.org/10.1145/2484239.2484275
    40 https://doi.org/10.1145/2594581
    41 https://doi.org/10.1145/2767386.2767442
    42 https://doi.org/10.1145/800222.806754
    43 schema:datePublished 2018-08-20
    44 schema:datePublishedReg 2018-08-20
    45 schema:description In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal.
    46 schema:genre research_article
    47 schema:inLanguage en
    48 schema:isAccessibleForFree false
    49 schema:isPartOf sg:journal.1052621
    50 schema:name Distributed exploration of dynamic rings
    51 schema:pagination 1-27
    52 schema:productId N2867bf01498a43c1a9b8011373aae514
    53 N2c37a24578de4c2fb9eb0b57ba8039ba
    54 Nbf866d7a8c024be283a02901a5a3f310
    55 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106255147
    56 https://doi.org/10.1007/s00446-018-0339-1
    57 schema:sdDatePublished 2019-04-10T14:05
    58 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    59 schema:sdPublisher Na6fcf50318674346bb97ba02d2d91345
    60 schema:url http://link.springer.com/10.1007/s00446-018-0339-1
    61 sgo:license sg:explorer/license/
    62 sgo:sdDataset articles
    63 rdf:type schema:ScholarlyArticle
    64 N2867bf01498a43c1a9b8011373aae514 schema:name dimensions_id
    65 schema:value pub.1106255147
    66 rdf:type schema:PropertyValue
    67 N2c37a24578de4c2fb9eb0b57ba8039ba schema:name readcube_id
    68 schema:value 65607d220d187190193961e119798717a945c146b03e31b0553888cec9f16784
    69 rdf:type schema:PropertyValue
    70 N38182e838a164bed8eae4d1fb56d5182 rdf:first sg:person.0610371471.49
    71 rdf:rest N81aabf6bedd74a9ebcca07d9271f5465
    72 N4e5366dfe8f042338a003a77a3ceaaae rdf:first sg:person.010566557723.84
    73 rdf:rest rdf:nil
    74 N76b356b2d76f408e82f1437f73d4f733 rdf:first sg:person.015542601431.41
    75 rdf:rest N38182e838a164bed8eae4d1fb56d5182
    76 N81aabf6bedd74a9ebcca07d9271f5465 rdf:first sg:person.011601470625.25
    77 rdf:rest N4e5366dfe8f042338a003a77a3ceaaae
    78 Na6fcf50318674346bb97ba02d2d91345 schema:name Springer Nature - SN SciGraph project
    79 rdf:type schema:Organization
    80 Nbf866d7a8c024be283a02901a5a3f310 schema:name doi
    81 schema:value 10.1007/s00446-018-0339-1
    82 rdf:type schema:PropertyValue
    83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Information and Computing Sciences
    85 rdf:type schema:DefinedTerm
    86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    87 schema:name Computation Theory and Mathematics
    88 rdf:type schema:DefinedTerm
    89 sg:journal.1052621 schema:issn 0178-2770
    90 1432-0452
    91 schema:name Distributed Computing
    92 rdf:type schema:Periodical
    93 sg:person.010566557723.84 schema:affiliation https://www.grid.ac/institutes/grid.34428.39
    94 schema:familyName Santoro
    95 schema:givenName N.
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010566557723.84
    97 rdf:type schema:Person
    98 sg:person.011601470625.25 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    99 schema:familyName Flocchini
    100 schema:givenName P.
    101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011601470625.25
    102 rdf:type schema:Person
    103 sg:person.015542601431.41 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
    104 schema:familyName Di Luna
    105 schema:givenName G.
    106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015542601431.41
    107 rdf:type schema:Person
    108 sg:person.0610371471.49 schema:affiliation https://www.grid.ac/institutes/grid.419303.c
    109 schema:familyName Dobrev
    110 schema:givenName S.
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0610371471.49
    112 rdf:type schema:Person
    113 sg:pub.10.1007/11945529_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047952182
    114 https://doi.org/10.1007/11945529_23
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/978-3-319-03578-9_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027423063
    117 https://doi.org/10.1007/978-3-319-03578-9_2
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/978-3-319-03850-6_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035063247
    120 https://doi.org/10.1007/978-3-319-03850-6_3
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-319-09620-9_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031791144
    123 https://doi.org/10.1007/978-3-319-09620-9_20
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/978-3-540-70575-8_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027002019
    126 https://doi.org/10.1007/978-3-540-70575-8_11
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/978-3-642-25873-2_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051713335
    129 https://doi.org/10.1007/978-3-642-25873-2_31
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-642-31104-8_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045024105
    132 https://doi.org/10.1007/978-3-642-31104-8_7
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/978-3-642-45249-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041512596
    135 https://doi.org/10.1007/978-3-642-45249-9_17
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/978-3-662-46018-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011019112
    138 https://doi.org/10.1007/978-3-662-46018-4_6
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-662-47672-7_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046778621
    141 https://doi.org/10.1007/978-3-662-47672-7_36
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/s00224-011-9341-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004728379
    144 https://doi.org/10.1007/s00224-011-9341-8
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/s00446-006-0154-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1000916693
    147 https://doi.org/10.1007/s00446-006-0154-y
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/s00446-011-0133-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031581381
    150 https://doi.org/10.1007/s00446-011-0133-9
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010742782
    153 rdf:type schema:CreativeWork
    154 https://doi.org/10.1006/jagm.1999.1043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014281330
    155 rdf:type schema:CreativeWork
    156 https://doi.org/10.1016/j.tcs.2005.07.014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006352716
    157 rdf:type schema:CreativeWork
    158 https://doi.org/10.1016/j.tcs.2007.05.011 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022545213
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/j.tcs.2008.02.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028600334
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1016/j.tcs.2012.10.029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012732800
    163 rdf:type schema:CreativeWork
    164 https://doi.org/10.1016/j.tcs.2012.11.022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006374898
    165 rdf:type schema:CreativeWork
    166 https://doi.org/10.1016/j.tcs.2013.01.025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033715963
    167 rdf:type schema:CreativeWork
    168 https://doi.org/10.1016/j.tcs.2014.07.013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008752835
    169 rdf:type schema:CreativeWork
    170 https://doi.org/10.1016/j.tcs.2016.04.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005155299
    171 rdf:type schema:CreativeWork
    172 https://doi.org/10.1016/s0895-7177(97)00050-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041577640
    173 rdf:type schema:CreativeWork
    174 https://doi.org/10.1080/17445760.2012.668546 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005693413
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1109/ipdps.2009.5161080 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093705627
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1109/mnet.2004.1337732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061411423
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1109/tc.2012.208 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061535334
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1109/tpds.2008.218 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753328
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1109/tpds.2011.33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061753875
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1137/s009753979732428x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880193
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1142/s0129054103001728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062896465
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1142/s0129054115500288 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897477
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1145/1806689.1806760 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046808496
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1145/1993806.1993808 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036726748
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1145/2484239.2484275 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030991275
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1145/2594581 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035640119
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1145/2767386.2767442 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018608128
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1145/800222.806754 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018316918
    203 rdf:type schema:CreativeWork
    204 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
    205 schema:name School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON, Canada
    206 rdf:type schema:Organization
    207 https://www.grid.ac/institutes/grid.34428.39 schema:alternateName Carleton University
    208 schema:name School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, ON, Canada
    209 rdf:type schema:Organization
    210 https://www.grid.ac/institutes/grid.419303.c schema:alternateName Slovak Academy of Sciences
    211 schema:name Slovak Academy of Sciences, Dúbravská cesta 9, 811 04, Bratislava, Slovakia
    212 rdf:type schema:Organization
     




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


    ...