[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Document Open Access Logo

Treasure Hunt with Barely Communicating Agents

Authors Stefan Dobrev, Rastislav Královic, Dana Pardubská

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.14.pdf
  • Filesize: 477 kB
  • 16 pages

Document Identifiers

Author Details

Stefan Dobrev
Rastislav Královic
Dana Pardubská

Cite As Get BibTex

Stefan Dobrev, Rastislav Královic, and Dana Pardubská. Treasure Hunt with Barely Communicating Agents. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.14

Abstract

We consider the problem of fault-tolerant parallel exhaustive search, a.k.a. “Treasure Hunt”, introduced by Fraigniaud, Korman and Rodeh in [13]: Imagine an infinite list of “boxes”, one of which contains a “treasure”. The ordering of the boxes reflects the importance of finding the treasure in a given box. There are k agents, whose goal is to locate the treasure in the least amount of time. The system is synchronous; at every step, an agent can ”open” a box and see whether the treasure is there. The hunt finishes when the first agent locates the treasure.
The original paper [13] considers non-cooperating randomized agents, out of which at most f can fail, with the failure pattern determined by an adversary. In this paper, we consider deterministic agents and investigate two failure models: The failing-agents model from [13] and a “black hole” model: At most f boxes contain “black holes”, placed by the adversary. When an agent opens a box containing a black hole, the agent disappears without an observable trace.
The crucial distinction, however, is that we consider “barely communicating” or “indirectly weakly communicating” agents: When an agent opens a box, it can tell whether the box has been previously opened. There are no other means of direct or indirect communication between the agents.
We show that adding even such weak means of communication has very strong impact on the solvability and complexity of the Treasure Hunt problem. In particular, in the failing agents model it allows the agents to be 1-competitive w.r.t. an optimal algorithm which does not know the location of the treasure, but is instantly notified of agent failures. In the black holes model
(where there is no deterministic solution for non-communicating agents even in the presence of a single black hole) we show a lower bound of 2f + 1 and an upper bound of 4f + 1 for the number of agents needed to solve Treasure Hunt in presence of up to f black holes, as well as partial results about the hunt time in the presence of few black holes.

Subject Classification

Keywords
  • parallel exhaustive search
  • treasure hunt
  • fault-tolerant search
  • weak coordination
  • black holes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Steve Alpern and Shmuel Gal. The Theory of Search Games and Rendezvous. International Series in Operations Research &Management Science. Springer US, 2006. Google Scholar
  2. David P. Anderson. Boinc: A system for public-resource computing and storage. In 5th IEEE/ACM International Workshop on Grid Computing, pages 4-10, 2004. URL: http://boinc.berkeley.edu.
  3. Ricardo Baeza-Yates and René Schott. Parallel searching in the plane. Computational Geometry, 5(3):143-154, 1995. URL: http://dx.doi.org/10.1016/0925-7721(95)00003-R.
  4. Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching with uncertainty extended abstract, pages 176-189. Springer Berlin Heidelberg, Berlin, Heidelberg, 1988. URL: http://dx.doi.org/10.1007/3-540-19487-8_20.
  5. Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J.E. Rawlins. Searching in the plane. Inf. Comput., 106(2):234-252, 1993. URL: http://dx.doi.org/10.1006/inco.1993.1054.
  6. Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Richard Královic, and Peter Rossmanith. On the power of randomness versus advice in online computation. In Henning Bordihn, Martin Kutrib, and Bianca Truthe, editors, Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday, volume 7300 of Lecture Notes in Computer Science, pages 30-43. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31644-9_2.
  7. Marek Chrobak, Leszek Gąsieniec, Thomas Gorry, and Russell Martin. Group Search on the Line, pages 164-176. Springer Berlin Heidelberg, Berlin, Heidelberg, 2015. URL: http://dx.doi.org/10.1007/978-3-662-46078-8_14.
  8. Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an infinite space with finite memory scouts. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 207-224. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.14.
  9. Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Computing, 19(1):1-99999, 2006. URL: http://dx.doi.org/10.1007/s00446-006-0154-y.
  10. Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. Algorithmica, 48(1):67-90, 2007. URL: http://dx.doi.org/10.1007/s00453-006-1232-z.
  11. Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines, pages 471-482. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_40.
  12. Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sebastien Sereni. Collaborative search on the plane without communication. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC '12, pages 77-86, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2332432.2332444.
  13. Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. Parallel exhaustive search without coordination. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 312-323. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897541.
  14. Chryssis Georgiou. Do-All Computing in Distributed Systems: Cooperation in the Presence of Adversity. Springer Publishing Company, Incorporated, 1st edition, 2010. Google Scholar
  15. Nicolas Hanusse, Dimitris J. Kavvadias, Evangelos Kranakis, and Danny Krizanc. Memoryless search algorithms in a network with faulty advice. Theor. Comput. Sci., 402(2-3):190-198, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.04.034.
  16. Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, pages 441-447, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=313559.313848.
  17. Dénes König. Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 77(4):453-465, 1916. URL: http://dx.doi.org/10.1007/BF01456961.
  18. Amos Korman and Yoav Rodeh. Parallel linear search with no coordination for a randomly placed treasure. CoRR, abs/1602.04952, 2016. URL: http://arxiv.org/abs/1602.04952.
  19. Amos Korman and Yoav Rodeh. Parallel search with no coordination. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, page to appear, 2017. Google Scholar
  20. Tobias Langner, Jara Uitto, David Stolz, and Roger Wattenhofer. Fault-Tolerant ANTS, pages 31-45. Springer Berlin Heidelberg, Berlin, Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-45174-8_3.
  21. Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Searching without communicating: tradeoffs between performance and selection complexity. Distributed Computing, pages 1-23, 2016. URL: http://dx.doi.org/10.1007/s00446-016-0283-x.
  22. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996. Google Scholar
  23. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00303-6.
  24. Mengfei Peng, Wei Shi, Jean-Pierre Corriveau, Richard Pazzi, and Yang Wang. Black hole search in computer networks: State-of-the-art, challenges and future directions. Journal of Parallel and Distributed Computing, 88:1-15, 2016. URL: http://dx.doi.org/10.1016/j.jpdc.2015.10.006.
  25. Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Trans. Algorithms, 10(3):12:1-12:15, 2014. URL: http://dx.doi.org/10.1145/2601068.
  26. Qin Xin. Faster treasure hunt and better strongly universal exploration sequences. CoRR, abs/1204.5442, 2012. URL: http://arxiv.org/abs/1204.5442.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact