Document Open Access Logo

The Complexity of the Distributed Constraint Satisfaction Problem

Authors Silvia Butti , Victor Dalmau

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.20.pdf
  • Filesize: 0.78 MB
  • 18 pages

Document Identifiers

Author Details

Silvia Butti
  • Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain
Victor Dalmau
  • Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain

Funding

  • Butti, Silvia: The project that gave rise to these results received the support of a fellowship from "la Caixa" Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713673.
  • Dalmau, Victor: Victor Dalmau was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22.

Acknowledgements

We would like to thank Gergely Neu for useful discussions on the weighted majority algorithm.

Cite As Get BibTex

Silvia Butti and Victor Dalmau. The Complexity of the Distributed Constraint Satisfaction Problem. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.20

Abstract

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template’s invariance under certain operations. Specifically, we show that DCSP(Γ) is polynomial-time tractable if and only if Γ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(Γ) in finite time. We also show that the same condition holds for the search variant of DCSP.
Collaterally, our results unveil a feature of the processes' neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • Constraint Satisfaction Problems
  • Distributed Algorithms
  • Polymorphisms

Metrics

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

Related Versions

References

  1. Dana Angluin. Local and global properties in networks of processors (extended abstract). In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 82-93. ACM, 1980. URL: https://doi.org/10.1145/800141.804655.
  2. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory Comput., 8(1):121-164, 2012. URL: https://doi.org/10.4086/toc.2012.v008a006.
  3. Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL: https://openreview.net/forum?id=r1lZ7AEKvB.
  4. Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  5. Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806.01261, 2018. URL: http://arxiv.org/abs/1806.01261.
  6. Ramon Bejar, Bhaskar Krishnamachari, Carla Gomes, and Bart Selman. Distributed constraint satisfaction in a wireless sensor tracking system. In Workshop on Distributed Constraint Reasoning, International Joint Conference on Artificial Intelligence, volume 4, 2001. Google Scholar
  7. Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, and Janos Simon. Symmetry breaking in anonymous networks: Characterizations. In Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, June 10-12, 1996, Proceedings, pages 16-26. IEEE Computer Society, 1996. Google Scholar
  8. Paolo Boldi and Sebastiano Vigna. An effective characterization of computability in anonymous networks. In Jennifer L. Welch, editor, Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, 2001, Proceedings, volume 2180 of Lecture Notes in Computer Science, pages 33-47. Springer, 2001. URL: https://doi.org/10.1007/3-540-45414-4_3.
  9. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  10. Ken R. Duffy, Charles Bordenave, and Douglas J. Leith. Decentralized constraint satisfaction. IEEE/ACM Trans. Netw., 21(4):1298-1308, 2013. URL: https://doi.org/10.1109/TNET.2012.2222923.
  11. Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization problems and applications: A survey. J. Artif. Intell. Res., 61:623-698, 2018. URL: https://doi.org/10.1613/jair.5565.
  12. Wan Fokkink. Distributed algorithms: an intuitive approach. MIT Press, 2013. Google Scholar
  13. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1-1:24, 2007. URL: https://doi.org/10.1145/1206035.1206036.
  14. Martin Grohe. word2vec, node2vec, graph2vec, x2vec: Towards a theory of vector embeddings of structured data. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 1-16. ACM, 2020. URL: https://doi.org/10.1145/3375395.3387641.
  15. Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. Van den Broeck, G.; Kersting, K.; Natarajan, S, 2017. Google Scholar
  16. Marcin Kozik. Solving CSPs using weak local consistency. SIAM Journal on Computing, to appear, 2020. URL: https://marcinkozik.staff.tcs.uj.edu.pl/Solving.CSPs.using.weak.local.consistency.pdf.
  17. Andrei A. Krokhin and Stanislav Živný, editors. The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-003-3.
  18. Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou. Linear programming, width-1 csps, and robust satisfaction. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 484-495. ACM, 2012. URL: https://doi.org/10.1145/2090236.2090274.
  19. Amnon Meisels. Distributed Search by Constrained Agents - Algorithms, Performance, Communication. Advanced Information and Knowledge Processing. Springer, 2008. URL: https://doi.org/10.1007/978-1-84800-040-7.
  20. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 4602-4609. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33014602.
  21. Francesca Rossi, Peter van Beek, and Toby Walsh, editors. Handbook of Constraint Programming, volume 2 of Foundations of Artificial Intelligence. Elsevier, 2006. URL: http://www.sciencedirect.com/science/bookseries/15746526/2.
  22. Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. RUN-CSP: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, abs/1909.08387, 2019. URL: http://arxiv.org/abs/1909.08387.
  23. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL: https://openreview.net/forum?id=ryGs6iA5Km.
  24. Masafumi Yamashita and Tiko Kameda. Computing on an anonymous network. In Danny Dolev, editor, Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, Toronto, Ontario, Canada, August 15-17, 1988, pages 117-130. ACM, 1988. URL: https://doi.org/10.1145/62546.62568.
  25. Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In Proceedings of the 12th International Conference on Distributed Computing Systems, Yokohama, Japan, June 9-12, 1992, pages 614-621. IEEE Computer Society, 1992. URL: https://doi.org/10.1109/ICDCS.1992.235101.
  26. Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Trans. Knowl. Data Eng., 10(5):673-685, 1998. URL: https://doi.org/10.1109/69.729707.
  27. Makoto Yokoo and Katsutoshi Hirayama. Algorithms for distributed constraint satisfaction: A review. Auton. Agents Multi Agent Syst., 3(2):185-207, 2000. URL: https://doi.org/10.1023/A:1010078712316.
  28. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.38.
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