Black hole search and exploration in unoriented tori with synchronous scattered finite automata
dc.creator | Markou, E. | en |
dc.creator | Paquette, M. | en |
dc.date.accessioned | 2015-11-23T10:38:59Z | |
dc.date.available | 2015-11-23T10:38:59Z | |
dc.date.issued | 2012 | |
dc.identifier | 10.1007/978-3-642-35476-2_17 | |
dc.identifier.isbn | 9783642354755 | |
dc.identifier.issn | 3029743 | |
dc.identifier.uri | http://hdl.handle.net/11615/30746 | |
dc.description.abstract | We consider the problem of locating a black hole in a synchronous, anonymous, and unoriented torus network using mobile agents. A black hole is a harmful network node that destroys any agent visiting it without leaving any trace. The objective is to locate the black hole using as few agents as possible. We present here an almost optimal deterministic algorithm for synchronous (partially) unoriented tori using five scattered agents with constant memory and three identical tokens. We also study the exploration problem of a safe (i.e., without black holes) unoriented torus. While it has been previously shown that there is no universal algorithm for one agent with constant memory and any constant number of tokens which can explore all cubic planar graphs, we give here the first algorithm which enables a finite automaton with two tokens to explore (without termination detection) any totally unoriented torus and we prove optimality on the number of tokens. © 2012 Springer-Verlag. | en |
dc.source.uri | http://www.scopus.com/inward/record.url?eid=2-s2.0-84871651885&partnerID=40&md5=29d5f5fc56126257a55937a7aceeaf32 | |
dc.subject | Anonymous Networks | en |
dc.subject | Black Hole Search | en |
dc.subject | Distributed Algorithms | en |
dc.subject | Fault Tolerance | en |
dc.subject | Finite State Automata | en |
dc.subject | Mobile Agents | en |
dc.subject | Black holes | en |
dc.subject | Cubic planar graphs | en |
dc.subject | Deterministic algorithms | en |
dc.subject | Network node | en |
dc.subject | Optimality | en |
dc.subject | Termination detection | en |
dc.subject | Torus networks | en |
dc.subject | Universal algorithm | en |
dc.subject | Algorithms | en |
dc.subject | Fault tolerant computer systems | en |
dc.subject | Finite automata | en |
dc.subject | Gravitation | en |
dc.subject | Optimization | en |
dc.subject | Parallel algorithms | en |
dc.subject | Stars | en |
dc.title | Black hole search and exploration in unoriented tori with synchronous scattered finite automata | en |
dc.type | other | en |
Αρχεία σε αυτό το τεκμήριο
Αρχεία | Μέγεθος | Τύπος | Προβολή |
---|---|---|---|
Δεν υπάρχουν αρχεία που να σχετίζονται με αυτό το τεκμήριο. |