Locating a Black Hole without the Knowledge of Incoming Link View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Peter Glaus

ABSTRACT

We study a group of mobile agents operating on an arbitrary unknown distributed system. One of the nodes of the distributed system is extremely harmful and destroys any incoming agent without notification. The task of exploring the distributed system and locating the harmful node, Black hole search, has been studied with various modifications. We are studying the effects of the knowledge of incoming link on the size of the optimal solution. When an agent enters a node, the information which port leads back can be given to it. We refer to this as to the knowledge of incoming link. In previous research, it was always assumed that the agent is given this information. In this paper we study arbitrary, unknown distributed systems without the knowledge of incoming link. Agents are asynchronous and they communicate via whiteboards. We present a lower bound on the size of the optimal solution, proving that at least agents are necessary to locate the black hole, with respect to the degree of the black hole Δ. We provide an algorithm for black hole search without the knowledge of incoming link as well. We prove that this algorithm is correct, and that it uses agents, thus providing optimal solution. More... »

PAGES

128-138

References to SciGraph publications

  • 2008. Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens in DISTRIBUTED COMPUTING
  • 2001. Mobile Search for a Black Hole in an Anonymous Ring in DISTRIBUTED COMPUTING
  • 2004. Multiple Agents RendezVous in a Ring in Spite of a Black Hole in PRINCIPLES OF DISTRIBUTED SYSTEMS
  • 2010. Black Hole Search in Directed Graphs in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2004. Improved Bounds for Optimal Black Hole Search with a Network Map in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 2007. Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links in DISTRIBUTED COMPUTING
  • Book

    TITLE

    Algorithmic Aspects of Wireless Sensor Networks

    ISBN

    978-3-642-05433-4
    978-3-642-05434-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-05434-1_13

    DOI

    http://dx.doi.org/10.1007/978-3-642-05434-1_13

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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": "Comenius University", 
              "id": "https://www.grid.ac/institutes/grid.7634.6", 
              "name": [
                "Department of Computer Science, Comenius University, Mlynska Dolina, 84248, Bratislava, Slovakia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Glaus", 
            "givenName": "Peter", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/571825.571853", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000958619"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27860-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006100921", 
              "https://doi.org/10.1007/978-3-540-27860-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27860-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006100921", 
              "https://doi.org/10.1007/978-3-540-27860-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20095", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015469195"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27796-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022687220", 
              "https://doi.org/10.1007/978-3-540-27796-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27796-5_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022687220", 
              "https://doi.org/10.1007/978-3-540-27796-5_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-87779-0_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023032737", 
              "https://doi.org/10.1007/978-3-540-87779-0_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45414-4_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024170729", 
              "https://doi.org/10.1007/3-540-45414-4_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75142-7_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032317348", 
              "https://doi.org/10.1007/978-3-540-75142-7_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-75142-7_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032317348", 
              "https://doi.org/10.1007/978-3-540-75142-7_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033891893", 
              "https://doi.org/10.1007/978-3-642-11476-2_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11476-2_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033891893", 
              "https://doi.org/10.1007/978-3-642-11476-2_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icdcs.2006.25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093904756"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009", 
        "datePublishedReg": "2009-01-01", 
        "description": "We study a group of mobile agents operating on an arbitrary unknown distributed system. One of the nodes of the distributed system is extremely harmful and destroys any incoming agent without notification. The task of exploring the distributed system and locating the harmful node, Black hole search, has been studied with various modifications. We are studying the effects of the knowledge of incoming link on the size of the optimal solution. When an agent enters a node, the information which port leads back can be given to it. We refer to this as to the knowledge of incoming link. In previous research, it was always assumed that the agent is given this information. In this paper we study arbitrary, unknown distributed systems without the knowledge of incoming link. Agents are asynchronous and they communicate via whiteboards. We present a lower bound on the size of the optimal solution, proving that at least agents are necessary to locate the black hole, with respect to the degree of the black hole \u0394. We provide an algorithm for black hole search without the knowledge of incoming link as well. We prove that this algorithm is correct, and that it uses agents, thus providing optimal solution.", 
        "editor": [
          {
            "familyName": "Dolev", 
            "givenName": "Shlomi", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-05434-1_13", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-05433-4", 
            "978-3-642-05434-1"
          ], 
          "name": "Algorithmic Aspects of Wireless Sensor Networks", 
          "type": "Book"
        }, 
        "name": "Locating a Black Hole without the Knowledge of Incoming Link", 
        "pagination": "128-138", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1017113003"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-05434-1_13"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5188aa74a08fa754fdd31f9b3b9ed8124ed9fd464fdce7e50b31931ee3b9aadc"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-05434-1_13", 
          "https://app.dimensions.ai/details/publication/pub.1017113003"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:31", 
        "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/0000000356_0000000356/records_57886_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-05434-1_13"
      }
    ]
     

    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-642-05434-1_13'

    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-642-05434-1_13'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-05434-1_13'

    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-642-05434-1_13'


     

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

    97 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-05434-1_13 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N6964c673e72241e38a26d13c3a470e56
    4 schema:citation sg:pub.10.1007/3-540-45414-4_12
    5 sg:pub.10.1007/978-3-540-27796-5_11
    6 sg:pub.10.1007/978-3-540-27860-3_6
    7 sg:pub.10.1007/978-3-540-75142-7_11
    8 sg:pub.10.1007/978-3-540-87779-0_16
    9 sg:pub.10.1007/978-3-642-11476-2_15
    10 https://doi.org/10.1002/net.20095
    11 https://doi.org/10.1109/icdcs.2006.25
    12 https://doi.org/10.1145/571825.571853
    13 schema:datePublished 2009
    14 schema:datePublishedReg 2009-01-01
    15 schema:description We study a group of mobile agents operating on an arbitrary unknown distributed system. One of the nodes of the distributed system is extremely harmful and destroys any incoming agent without notification. The task of exploring the distributed system and locating the harmful node, Black hole search, has been studied with various modifications. We are studying the effects of the knowledge of incoming link on the size of the optimal solution. When an agent enters a node, the information which port leads back can be given to it. We refer to this as to the knowledge of incoming link. In previous research, it was always assumed that the agent is given this information. In this paper we study arbitrary, unknown distributed systems without the knowledge of incoming link. Agents are asynchronous and they communicate via whiteboards. We present a lower bound on the size of the optimal solution, proving that at least agents are necessary to locate the black hole, with respect to the degree of the black hole Δ. We provide an algorithm for black hole search without the knowledge of incoming link as well. We prove that this algorithm is correct, and that it uses agents, thus providing optimal solution.
    16 schema:editor Nd9494d82f0f04810b9949bcc093d092a
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf Nfeaab94510ce4f67898df04052f16f0c
    21 schema:name Locating a Black Hole without the Knowledge of Incoming Link
    22 schema:pagination 128-138
    23 schema:productId N78d7cd7eef9f4b8c907b5b134036634e
    24 Nd507c576929b4bb29ff13403ec41c83c
    25 Nfb850c18755b41ecba8f1665f5d7c160
    26 schema:publisher N750269cd18da42e78caac4b782818783
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017113003
    28 https://doi.org/10.1007/978-3-642-05434-1_13
    29 schema:sdDatePublished 2019-04-16T07:31
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N8ded322df9684683b74b147277b704e0
    32 schema:url https://link.springer.com/10.1007%2F978-3-642-05434-1_13
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N4954fd32876442df951555d05d4b366c schema:affiliation https://www.grid.ac/institutes/grid.7634.6
    37 schema:familyName Glaus
    38 schema:givenName Peter
    39 rdf:type schema:Person
    40 N6964c673e72241e38a26d13c3a470e56 rdf:first N4954fd32876442df951555d05d4b366c
    41 rdf:rest rdf:nil
    42 N750269cd18da42e78caac4b782818783 schema:location Berlin, Heidelberg
    43 schema:name Springer Berlin Heidelberg
    44 rdf:type schema:Organisation
    45 N78d7cd7eef9f4b8c907b5b134036634e schema:name readcube_id
    46 schema:value 5188aa74a08fa754fdd31f9b3b9ed8124ed9fd464fdce7e50b31931ee3b9aadc
    47 rdf:type schema:PropertyValue
    48 N8ded322df9684683b74b147277b704e0 schema:name Springer Nature - SN SciGraph project
    49 rdf:type schema:Organization
    50 Nc9f3cef04ebb41a1be512bd21e27c7e1 schema:familyName Dolev
    51 schema:givenName Shlomi
    52 rdf:type schema:Person
    53 Nd507c576929b4bb29ff13403ec41c83c schema:name doi
    54 schema:value 10.1007/978-3-642-05434-1_13
    55 rdf:type schema:PropertyValue
    56 Nd9494d82f0f04810b9949bcc093d092a rdf:first Nc9f3cef04ebb41a1be512bd21e27c7e1
    57 rdf:rest rdf:nil
    58 Nfb850c18755b41ecba8f1665f5d7c160 schema:name dimensions_id
    59 schema:value pub.1017113003
    60 rdf:type schema:PropertyValue
    61 Nfeaab94510ce4f67898df04052f16f0c schema:isbn 978-3-642-05433-4
    62 978-3-642-05434-1
    63 schema:name Algorithmic Aspects of Wireless Sensor Networks
    64 rdf:type schema:Book
    65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Information and Computing Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information Systems
    70 rdf:type schema:DefinedTerm
    71 sg:pub.10.1007/3-540-45414-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024170729
    72 https://doi.org/10.1007/3-540-45414-4_12
    73 rdf:type schema:CreativeWork
    74 sg:pub.10.1007/978-3-540-27796-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022687220
    75 https://doi.org/10.1007/978-3-540-27796-5_11
    76 rdf:type schema:CreativeWork
    77 sg:pub.10.1007/978-3-540-27860-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006100921
    78 https://doi.org/10.1007/978-3-540-27860-3_6
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/978-3-540-75142-7_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032317348
    81 https://doi.org/10.1007/978-3-540-75142-7_11
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/978-3-540-87779-0_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023032737
    84 https://doi.org/10.1007/978-3-540-87779-0_16
    85 rdf:type schema:CreativeWork
    86 sg:pub.10.1007/978-3-642-11476-2_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033891893
    87 https://doi.org/10.1007/978-3-642-11476-2_15
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1002/net.20095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015469195
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/icdcs.2006.25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093904756
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1145/571825.571853 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000958619
    94 rdf:type schema:CreativeWork
    95 https://www.grid.ac/institutes/grid.7634.6 schema:alternateName Comenius University
    96 schema:name Department of Computer Science, Comenius University, Mlynska Dolina, 84248, Bratislava, Slovakia
    97 rdf:type schema:Organization
     




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


    ...