Document Open Access Logo

Byzantine Gathering in Polynomial Time

Authors Sébastien Bouchard, Yoann Dieudonné, Anissa Lamani



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.147.pdf
  • Filesize: 429 kB
  • 15 pages

Document Identifiers

Author Details

Sébastien Bouchard
  • Sorbonne Universités, UPMC Univ Paris 06, CNRS, INRIA, LIP6 UMR 7606, Paris, France
Yoann Dieudonné
  • Laboratoire MIS & Université de Picardie Jules Verne, Amiens, France
Anissa Lamani
  • Laboratoire MIS & Université de Picardie Jules Verne, Amiens, France

Cite AsGet BibTex

Sébastien Bouchard, Yoann Dieudonné, and Anissa Lamani. Byzantine Gathering in Polynomial Time. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.147

Abstract

Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile systems. This can be made drastically more difficult to achieve when some agents are subject to faults, especially the Byzantine ones that are known as being the worst faults to handle. In this paper we study, from a deterministic point of view, the task of Byzantine gathering in a network modeled as a graph. In other words, despite the presence of Byzantine agents, all the other (good) agents, starting from {possibly} different nodes and applying the same deterministic algorithm, have to meet at the same node in finite time and stop moving. An adversary chooses the initial nodes of the agents (the number of agents may be larger than the number of nodes) and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label. The agents move in synchronous rounds and can communicate with each other only when located at the same node. Within the team, f of the agents are Byzantine. A Byzantine agent acts in an unpredictable and arbitrary way. For example, it can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. Besides its label, which corresponds to a local knowledge, an agent is assigned some global knowledge denoted by GK that is common to all agents. In literature, the Byzantine gathering problem has been analyzed in arbitrary n-node graphs by considering the scenario when GK=(n,f) and the scenario when GK=f. In the first (resp. second) scenario, it has been shown that the minimum number of good agents guaranteeing deterministic gathering of all of them is f+1 (resp. f+2). However, for both these scenarios, all the existing deterministic algorithms, whether or not they are optimal in terms of required number of good agents, have the major disadvantage of having a time complexity that is exponential in n and L, where L is the value of the largest label belonging to a good agent. In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession on the proportion of Byzantine agents within the team, but that offers a significantly lower complexity. We also seek to use a global knowledge whose the length of the binary representation (that we also call size) is small. In this respect, assuming that the agents are in a strong team i.e., a team in which the number of good agents is at least some prescribed value that is quadratic in f, we give positive and negative results. On the positive side, we show an algorithm that solves Byzantine gathering with all strong teams in all graphs of size at most n, for any integers n and f, in a time polynomial in n and the length |l_{min}| of the binary representation of the smallest label of a good agent. The algorithm works using a global knowledge of size O(log log log n), which is of optimal order of magnitude in our context to reach a time complexity that is polynomial in n and |l_{min}|. Indeed, on the negative side, we show that there is no deterministic algorithm solving Byzantine gathering with all strong teams, in all graphs of size at most n, in a time polynomial in n and |l_{min}| and using a global knowledge of size o(log log log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Computing methodologies → Mobile agents
Keywords
  • gathering
  • deterministic algorithm
  • mobile agent
  • Byzantine fault
  • polynomial time

Metrics

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

References

  1. Serge Abiteboul, Haim Kaplan, and Tova Milo. Compact labeling schemes for ancestor queries. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 547-556, 2001. Google Scholar
  2. Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput., 36(1):56-82, 2006. Google Scholar
  3. Steve Alpern. Rendezvous search: A personal perspective. Operations Research, 50(5):772-795, 2002. Google Scholar
  4. Steve Alpern. The theory of search games and rendezvous. International Series in Operations Research and Management Science, Kluwer Academic Publishers, 2003. Google Scholar
  5. Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, and Arnaud Labourel. Almost optimal asynchronous rendezvous in infinite multidimensional grids. In Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, pages 297-311, 2010. Google Scholar
  6. Michael Barborak and Miroslaw Malek. The consensus problem in fault-tolerant computing. ACM Comput. Surv., 25(2):171-220, 1993. Google Scholar
  7. Sébastien Bouchard, Yoann Dieudonné, and Bertrand Ducourthial. Byzantine gathering in networks. Distributed Computing, 29(6):435-457, 2016. Google Scholar
  8. Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by mobile robots: Gathering. SIAM J. Comput., 41(4):829-879, 2012. Google Scholar
  9. Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, and David Peleg. Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms, 4(4):42:1-42:18, 2008. Google Scholar
  10. Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, and Arnaud Labourel. Tell me where I am so I can meet you sooner. In Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, pages 502-514, 2010. Google Scholar
  11. Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende. Search on a line by byzantine robots. In 27th International Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia, pages 27:1-27:12, 2016. Google Scholar
  12. Jurek Czyzowicz, Adrian Kosowski, and Andrzej Pelc. How to meet when you forget: log-space rendezvous in arbitrary graphs. Distributed Computing, 25(2):165-178, 2012. Google Scholar
  13. Jurek Czyzowicz, Andrzej Pelc, and Arnaud Labourel. How to meet asynchronously (almost) everywhere. ACM Transactions on Algorithms, 8(4):37, 2012. Google Scholar
  14. Shantanu Das, Dariusz Dereniowski, Adrian Kosowski, and Przemyslaw Uznanski. Rendezvous of distance-aware mobile agents in unknown graphs. In Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, pages 295-310, 2014. Google Scholar
  15. Xavier Défago, Maria Gradinariu, Stéphane Messika, and Philippe Raipin Parvédy. Fault-tolerant and self-stabilizing mobile robots gathering. In Distributed Computing, 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18-20, 2006, Proceedings, pages 46-60, 2006. Google Scholar
  16. Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. Algorithmica, 46(1):69-96, 2006. Google Scholar
  17. Yoann Dieudonné, Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on Algorithms, 11(1):1, 2014. Google Scholar
  18. Yoann Dieudonné, Andrzej Pelc, and Vincent Villain. How to meet asynchronously at polynomial cost. SIAM J. Comput., 44(3):844-867, 2015. Google Scholar
  19. Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Computing, 21(6):395-403, 2009. Google Scholar
  20. Pierre Fraigniaud, David Ilcinkas, and Andrzej Pelc. Tree exploration with advice. Inf. Comput., 206(11):1276-1287, 2008. Google Scholar
  21. Pierre Fraigniaud and Andrzej Pelc. Deterministic rendezvous in trees with little memory. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, pages 242-256, 2008. Google Scholar
  22. Pierre Fraigniaud and Andrzej Pelc. Delays induce an exponential memory gap for rendezvous in trees. ACM Transactions on Algorithms, 9(2):17, 2013. Google Scholar
  23. Samuel Guilbault and Andrzej Pelc. Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theor. Comput. Sci., 509:86-96, 2013. Google Scholar
  24. Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, and Masafumi Yamashita. The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput., 41(1):26-46, 2012. Google Scholar
  25. Michal Katz, Nir A. Katz, Amos Korman, and David Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23-40, 2004. Google Scholar
  26. Dariusz R. Kowalski and Adam Malinowski. How to meet in anonymous network. Theor. Comput. Sci., 399(1-2):141-156, 2008. Google Scholar
  27. Evangelos Kranakis, Danny Krizanc, Euripides Markou, Aris Pagourtzis, and Felipe Ramírez. Different speeds suffice for rendezvous of two agents on arbitrary graphs. In SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings, pages 79-90, 2017. Google Scholar
  28. Evangelos Kranakis, Danny Krizanc, and Sergio Rajsbaum. Mobile agent rendezvous: A survey. In Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings, pages 1-9, 2006. Google Scholar
  29. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  30. Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, and Ugo Vaccaro. Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci., 355(3):315-326, 2006. Google Scholar
  31. Avery Miller and Andrzej Pelc. Fast rendezvous with advice. Theor. Comput. Sci., 608:190-198, 2015. Google Scholar
  32. Avery Miller and Andrzej Pelc. Time versus cost tradeoffs for deterministic rendezvous in networks. Distributed Computing, 29(1):51-64, 2016. Google Scholar
  33. Nicolas Nisse and David Soguet. Graph searching with advice. Theor. Comput. Sci., 410(14):1307-1318, 2009. Google Scholar
  34. Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228-234, 1980. Google Scholar
  35. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. Google Scholar
  36. Thomas Schelling. The Strategy of Conflict. Oxford University Press, Oxford, 1960. Google Scholar
  37. Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms, 10(3):12, 2014. Google Scholar
  38. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. 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