{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T15:00:20Z","timestamp":1710255620552},"reference-count":23,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2005,12,12]],"date-time":"2005-12-12T00:00:00Z","timestamp":1134345600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2006,3]]},"abstract":"Abstract<\/jats:title>Mobile agents operating in networked environments face threats from other agents as well as from the hosts (i.e., network sites) they visit. A black<\/jats:italic> hole is a harmful host that destroys incoming agents without leaving any trace. To determine the location of such a harmful host is a dangerous but crucial task, called black<\/jats:italic> hole search. The most important parameter for a solution strategy is the number of agents it requires (the size<\/jats:italic>); the other parameter of interest is the total number of moves performed by the agents (the cost<\/jats:italic>). It is known that at least two<\/jats:italic> agents are needed; furthermore, with full topological knowledge, \u03a9(n<\/jats:italic> log n<\/jats:italic>) moves are required in arbitrary<\/jats:italic> networks. The natural question is whether, in specific<\/jats:italic> networks, it is possible to obtain (topology\u2010dependent but) more cost efficient solutions. It is known that this is not the case for rings. In this article, we show that this negative result does not generalizes. In fact, we present a general strategy that allows two<\/jats:italic> agents to locate the black hole with O<\/jats:italic>(n<\/jats:italic>) moves in common interconnection networks: hypercubes<\/jats:italic>, cube\u2010connected cycles<\/jats:italic>, star graphs<\/jats:italic>, wrapped butterflies<\/jats:italic>, chordal rings<\/jats:italic>, as well as in multidimensional meshes<\/jats:italic> and tori<\/jats:italic> of restricted diameter. These results hold even if the networks are anonymous. \u00a9 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 61\u201371 2006<\/jats:p>","DOI":"10.1002\/net.20095","type":"journal-article","created":{"date-parts":[[2005,12,12]],"date-time":"2005-12-12T19:16:40Z","timestamp":1134415000000},"page":"61-71","source":"Crossref","is-referenced-by-count":45,"title":["Black hole search in common interconnection networks"],"prefix":"10.1002","volume":"47","author":[{"given":"S.","family":"Dobrev","sequence":"first","affiliation":[]},{"given":"P.","family":"Flocchini","sequence":"additional","affiliation":[]},{"given":"R.","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[]},{"given":"P.","family":"Ru\u017ei\u010dka","sequence":"additional","affiliation":[]},{"given":"G.","family":"Prencipe","sequence":"additional","affiliation":[]},{"given":"N.","family":"Santoro","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,1,12]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"e_1_2_1_3_2","article-title":"The data grid: Towards an architecture for the distributed management and analysis of large scientific dataset","author":"Allcock W.","year":"2002","journal-title":"J Network Comput Appl"},{"key":"e_1_2_1_4_2","unstructured":"E.Arkin M.Bender S.Fekete J.Mitchell \u201cThe freeze\u2010tag problem: How to wake up a swarm of robots \u201d 13th ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '02) 2002 pp.568\u2013577."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"D.M.Chess \u201cSecurity issues in mobile code systems \u201d Conference on Mobile Agent Security LNCS 1419 1998 pp.1\u201314.","DOI":"10.1007\/3-540-68671-1_1"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"A.Dessmark P.Fraigniaud A.Pelc \u201cDeterministic rendezvous in graphs \u201d 11th Annual European Symposium on Algorithms (ESA '03) 2003 pp.184\u2013195.","DOI":"10.1007\/978-3-540-39658-1_19"},{"key":"e_1_2_1_7_2","unstructured":"K.Diks P.Fraigniaud E.Kranakis A.Pelc \u201cTree exploration with little memory \u201d 13th ACM\u2010SIAM Symposium on Discrete Algorithms (SODA '02) 2002 pp.588\u2013597."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"S.Dobrev P.Flocchini G.Prencipe N.Santoro \u201cMobile agents searching for a black hole in an anonymous ring \u201d 15th Int. Symposium on Distributed Computing (DISC 2001) 2001 pp.166\u2013179.","DOI":"10.1007\/3-540-45414-4_12"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"S.Dobrev P.Flocchini G.Prencipe N.Santoro \u201cFinding a black hole in an arbitrary network: Optimal mobile agents protocols \u201d 21st ACM Symposium on Principles of Distributed Computing (PODC 2002) 2002 pp.153\u2013162.","DOI":"10.1145\/571825.571853"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"P.Fraigniaud L.Ga\u0327sieniec D.R.Kowalski A.Pelc \u201cCollective tree exploration \u201d 6th Latin American Theoretical Informatics Symposium 2004 2004 pp.141\u2013151.","DOI":"10.1007\/978-3-540-24698-5_18"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"P.Fraigniaud D.Ilcinkas \u201cDirected graph exploration with little memory \u201d 21st Symposium on Theoretical Aspects of Computer Science (STACS 2004) 2004 pp.246\u2013257.","DOI":"10.1007\/978-3-540-24749-4_22"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/35.689634"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"N.Hanusse D.Kavvadias E.Kranakis D.Krizanc \u201cMemoryless search algorithms in a network with faulty advice \u201d 2nd IFIP International Conference on Theoretical Computer Science (TCS '02) 2002 pp.206\u2013216.","DOI":"10.1007\/978-0-387-35608-2_18"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"F.Hohl \u201cTime limited blackbox security: Protecting mobile agents from malicious hosts \u201d Conference on Mobile Agent Security LNCS 1419 1998 pp.92\u2013113.","DOI":"10.1007\/3-540-68671-1_6"},{"key":"e_1_2_1_15_2","unstructured":"F.Hohl \u201cA framework to protect mobile agents by using reference states \u201d 20th International Conference on Distributed Computing Systems (ICDCS 2000) 2000."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"L.M.Kirousis E.Kranakis D.Krizanc Y.Stamatiou \u201cLocating information with uncertainty in fully interconnected networks \u201d 14th International Symposium on Distributed Computing (DISC 2000) LNCS 1914 2000 pp.283\u2013296.","DOI":"10.1007\/3-540-40026-5_19"},{"key":"e_1_2_1_17_2","volume-title":"Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes","author":"Leighton F.T.","year":"1992"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-3664(99)00083-3"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1043"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"T.Sander C.F.Tschudin \u201cProtecting mobile agents against malicious hosts \u201d Conference on Mobile Agent Security LNCS 1419 1998 pp.44\u201360.","DOI":"10.1007\/3-540-68671-1_4"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"K.Schelderup J.Ones \u201cMobile agent security\u2014Issues and directions \u201d 6th Int. Conf. on Intelligence and Services in Networks LNCS 1597 1999 pp.155\u2013167.","DOI":"10.1007\/3-540-48888-X_16"},{"key":"e_1_2_1_22_2","unstructured":"S.K.Ng K.W.Cheung \u201cProtecting mobile agents against malicious hosts by intention spreading \u201d 1999 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'99) 1999 pp.725\u2013729."},{"key":"e_1_2_1_23_2","volume-title":"Mobile objects","author":"Vitek J.","year":"1999"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"X.Yu M.Yung \u201cAgent rendezvous: A dynamic symmetry\u2010breaking problem \u201d 23rd International Colloquium on Automata Languages and Programming (ICALP '96) LNCS 1099 1996 pp.610\u2013621.","DOI":"10.1007\/3-540-61440-0_163"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20095","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T09:50:52Z","timestamp":1700041852000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,12]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1002\/net.20095"],"URL":"https:\/\/doi.org\/10.1002\/net.20095","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1,12]]}}}