Document Open Access Logo

On Memory, Communication, and Synchronous Schedulers When Moving and Computing

Authors Paola Flocchini, Nicola Santoro, Koichi Wada

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.25.pdf
  • Filesize: 0.97 MB
  • 17 pages

Document Identifiers

Author Details

Paola Flocchini
  • EECS, University of Ottawa, Canada
Nicola Santoro
  • School of Computer Science, Carleton University, Canada
Koichi Wada
  • Faculty of Science and Engineering, Hosei University, Japan

Acknowledgements

This research was partly supported by NSERC through the Discovery Grant program, by Prof. Flocchini’s University Research Chair, by JSPS KAKENHI No. 17K00019, and by Japan Science and Technology Agency (JST) SICORP Grant#JPMJSC1806.

Cite AsGet BibTex

Paola Flocchini, Nicola Santoro, and Koichi Wada. On Memory, Communication, and Synchronous Schedulers When Moving and Computing. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.25

Abstract

We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Look-Compute-Move
  • Oblivious mobile robots
  • Robots with lights
  • Memory versus Communication
  • Moving and Computing

Metrics

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

References

  1. N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing, 36(1):56-82, 2006. Google Scholar
  2. H. Ando, Y. Osawa, I. Suzuki, and M. Yamashita. A distributed memoryless point concergence algorithm for mobile robots with limited visivility. IEEE Transactions on Robotics and Automation, 15(5):818-828, 1999. Google Scholar
  3. S. Bhagat and K. Mukhopadhyaya. Optimum algorithm for mutual visibility among asynchronous robots with lights. In Proc. of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 341-355, 2017. Google Scholar
  4. Z. Bouzid, S. Das, and S. Tixeuil. Gathering of mobile robots tolerating multiple crash Faults. In the 33rd Int. Conf. on Distributed Computing Systems (ICDCS), pages 334-346, 2013. Google Scholar
  5. D. Canepa and M. Gradinariu Potop-Butucaru. Stabilizing flocking via leader election in robot networks. In Proc. of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 52-66, 2007. Google Scholar
  6. S. Cicerone, Di Stefano, and A. Navarra. Gathering of robots on meeting-points. Distributed Computing, 31(1):1-50, 2018. Google Scholar
  7. M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by mobile robots: Gathering. sicomp, 41(4):829-879, 2012. Google Scholar
  8. R. Cohen and D. Peleg. Convergence properties of the gravitational algorithms in asynchronous robot systems. sicomp, 34(15):1516-1528, 2005. Google Scholar
  9. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The power of lights: synchronizing asynchronous robots using visible bits. In Proc. of the 32nd International Conference on Distributed Computing Systems (ICDCS), pages 506-515, 2012. Google Scholar
  10. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609:171-184, 2016. Google Scholar
  11. G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254(3):392-418, 2017. Google Scholar
  12. G.A. Di Luna and G. Viglietta. Robots with Lights. Chapter 11 of [12], pages 252-277, 2019. Google Scholar
  13. P. Flocchini, G. Prencipe, and N. Santoro (Eds). Distributed Computing by Mobile Entities. Springer, 2019. Google Scholar
  14. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots. In Proc. of 10th International Symposium on Algorithms and Computation (ISAAC), pages 93-102, 1999. Google Scholar
  15. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots with limited visibility. tcs, 337(1-3):147-169, 2005. Google Scholar
  16. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Arbitrary pattern formation by asynchronous oblivious robots. tcs, 407:412-447, 2008. Google Scholar
  17. P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita. Rendezvous with Constant Memory. tcs, 621:57-72, 2016. Google Scholar
  18. N. Fujinaga, Y. Yamauchi, H. Ono, S. Kijima, and M. Yamashita. Pattern formation by oblivious asynchronous mobile robots. sicomp, 44(3):740-785, 2015. Google Scholar
  19. V. Gervasi and G. Prencipe. Coordination without communication: The case of the flocking problem. Discrete Applied Mathematics, 144(3):324-344, 2004. Google Scholar
  20. A. Hériban, X. Défago, and S. Tixeuil. Optimally gathering two robots. In Proc. of the 19th Int. Conference on Distributed Computing and Networking (ICDCN), pages 1-10, 2018. Google Scholar
  21. T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago, K. Wada, and M. Yamashita. The gathering problem for two oblivious robots with unreliable compasses. sicomp, 41(1):26-46, 2012. Google Scholar
  22. T. Okumura, K. Wada, and X. Défago. Optimal Rendezvous ℒ-Algorithms for Asynchronous Mobile Robots with External-Lights. In Proc. of the 22nd Int. Conference on Principles of Distributed Systems (OPODIS), pages 24:1-24:16, 2018. Google Scholar
  23. T. Okumura, K. Wada, and Y. Katayama. Brief Announcement: Optimal asynchronous Rendezvous for mobile robots with lights. In Proc. of the 19th Int. Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 484-488, 2017. Google Scholar
  24. D. Peleg. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In Proc. of 7th International Workshop on Distributed Computing (IWDC), pages 1-12, 2005. Google Scholar
  25. G. Sharma, R. Alsaedi, C. Bush, and S. Mukhopadyay. The complete visibility problem for fat robots with lights. In Proc. of the 19th International Conference on Distributed Computing and Networking (ICDCN), pages 21:1-21:4, 2018. Google Scholar
  26. S. Souissi, T. Izumi, and K. Wada. Oracle-based flocking of mobile robots in crash-recovery model. In Proc. of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 683-697, 2009. Google Scholar
  27. I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. sicomp, 28:1347-1363, 1999. Google Scholar
  28. S. Terai, K. Wada, and Y. Katayama. Gathering problems for autonomous mobile robots with lights. arXiv.org, cs(ArXiv:1811.12068), 2018. Google Scholar
  29. G. Viglietta. Rendezvous of two robots with visible bits. In 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pages 291-306, 2013. Google Scholar
  30. M. Yamashita and I. Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. tcs, 411(26-28):2433-2453, 2010. Google Scholar
  31. Y. Yamauchi, T. Uehara, S. Kijima, and M. Yamashita. Plane formation by synchronous mobile robots in the three-dimensional euclidean space. Journal of the ACM (JACM), 64:3(16):16:1-16:43, 2017. Google Scholar
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 Imprint Privacy Contact