{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:23:37Z","timestamp":1772083417383,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T00:00:00Z","timestamp":1657238400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T00:00:00Z","timestamp":1657238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010434","name":"\u201dla caixa\u201d foundation","doi-asserted-by":"publisher","award":["713673"],"award-info":[{"award-number":["713673"]}],"id":[{"id":"10.13039\/100010434","id-type":"DOI","asserted-by":"publisher"}]},{"name":"miccin","award":["TIN2016-76573-C2-1P and PID2019-109137GB-C22"],"award-info":[{"award-number":["TIN2016-76573-C2-1P and PID2019-109137GB-C22"]}]},{"DOI":"10.13039\/100018967","name":"Universitat Pompeu Fabra","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018967","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2019s invariance under certain operations. Specifically, we show that DCSP(\u0393) is polynomial-time tractable if and only if \u0393 is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP(\u0393) 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\u2019 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.<\/jats:p>","DOI":"10.1007\/s00224-022-10091-y","type":"journal-article","created":{"date-parts":[[2022,7,8]],"date-time":"2022-07-08T11:02:54Z","timestamp":1657278174000},"page":"838-867","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of the Distributed Constraint Satisfaction Problem"],"prefix":"10.1007","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0171-2021","authenticated-orcid":false,"given":"Silvia","family":"Butti","sequence":"first","affiliation":[]},{"given":"V\u00edctor","family":"Dalmau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,8]]},"reference":[{"key":"10091_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and Global Properties in Networks of Processors (Extended Abstract). In: Miller, R.E., Ginsburg, S., Burkhard, W.A., Lipton, R.J. (eds.) Proceedings of the 12th Annual ACM Symposium on Theory of Computing. April 28-30, 1980, Los Angeles, California, USA, pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"issue":"1","key":"10091_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The Multiplicative Weights Update Method: a meta-Algorithm and Applications. Theory Comput. 8(1), 121\u2013164 (2012)","journal-title":"Theory Comput."},{"key":"10091_CR3","unstructured":"Barcel\u00f3, P., Kostylev, E., Monet, M., P\u00e9rez, J., Reutter, J.L., Silva, J.P.: 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)"},{"issue":"3","key":"10091_CR4","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1017\/bsl.2015.25","volume":"21","author":"L Barto","year":"2015","unstructured":"Barto, L.: The constraint satisfaction problem and universal algebra. Bull. Symb. Log. 21(3), 319\u2013337 (2015)","journal-title":"Bull. Symb. Log."},{"key":"10091_CR5","unstructured":"Barto, L., Krokhin, A.A., Willard, R.: Polymorphisms, and how to use them. In: Krokhin, A.A., Zivn\u00fd, S. (eds.) The Constraint Satisfaction Problem: Complexity and Approximability, vol. 7 of Dagstuhl Follow-Ups. pp. 1\u201344. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"10091_CR6","unstructured":"Battaglia, P.W., Hamrick, J.B., Bapst, V., Sanchez-Gonzalez, A., Flores Zambaldi, V., Malinowski, M., Tacchetti, A., Raposo, D., Santoro, A., Faulkner, R., G\u00fcl\u00e7ehre, C., Francis Song, H., Ballard, A.J., Gilmer, J., Dahl, G.E., Vaswani, A., Allen, K.R., Nash, C., Langston, V., Dyer, C., Heess, N., Wierstra, D., Kohli, P., Botvinick, M., Vinyals, O., Li, Y., Pascanu, R.: Relational inductive biases, deep learning, and graph networks. CoRR, abs\/1806.01261 (2018)"},{"key":"10091_CR7","unstructured":"Bejar, R., Krishnamachari, B., Gomes, Carla, G., Selman, B.: Distributed constraint satisfaction in a wireless sensor tracking system. In: Workshop on distributed constraint reasoning, international joint conference on artificial intelligence. vol. 4 (2001)"},{"key":"10091_CR8","unstructured":"Boldi, P., Shammah, S., Vigna, S., Codenotti, B., Gemmell, P., Simon, J.: 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. pp. 16\u201326. IEEE Computer Society (1996)"},{"key":"10091_CR9","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Welch, J.L. (ed.) Distributed computing, 15th international conference, DISC 2001, Lisbon, Portugal. October 3-5, 2001, Proceedings. vol. 2180 of Lecture Notes in Computer Science, pp. 33\u201347. Springer (2001)","DOI":"10.1007\/3-540-45414-4_3"},{"key":"10091_CR10","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A Dichotomy theorem for nonuniform csps. In: Chris Umans (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, Berkeley, CA, USA, October 15-17, 2017, pp. 319\u2013330. IEEE, Computer Society (2017)","DOI":"10.1109\/FOCS.2017.37"},{"issue":"4","key":"10091_CR11","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1109\/TNET.2012.2222923","volume":"21","author":"KR Duffy","year":"2013","unstructured":"Duffy, K.R., Bordenave, C., Leith, D.J.: Decentralized Constraint Satisfaction. IEEE\/ACM Trans. Netw. 21(4), 1298\u20131308 (2013)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"10091_CR12","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1613\/jair.5565","volume":"61","author":"F Fioretto","year":"2018","unstructured":"Fioretto, F., Pontelli, E., Yeoh, W.: Distributed constraint optimization problems and applications: A survey. J. Artif. Intell. Res. 61, 623\u2013698 (2018)","journal-title":"J. Artif. Intell. Res."},{"key":"10091_CR13","unstructured":"Fokkink, W.: Distributed algorithms: An intuitive approach MIT Press (2013)"},{"issue":"1","key":"10091_CR14","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The Complexity of homomorphism and constraint satisfaction problems seen from the Other side. J. ACM 54(1), 1:1\u20131:24 (2007)","journal-title":"J. ACM"},{"key":"10091_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: 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. pp. 1\u201316. ACM (2020)","DOI":"10.1145\/3375395.3387641"},{"key":"10091_CR16","unstructured":"Martin Grohe, M., Kersting, K., Mladenov, M., Schweitzer, P.: Color refinement and its applications. Van den Broeck, G.; Kersting, K.; Natarajan, S (2017)"},{"key":"10091_CR17","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.jcss.2016.07.008","volume":"84","author":"P Jonsson","year":"2017","unstructured":"Jonsson, P., Lagerkvist, V., Nordh, G., Zanuttini, B.: Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci. 84, 52\u201378 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10091_CR18","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/18M117577X","volume":"50","author":"M Kozik","year":"2021","unstructured":"Kozik, M.: Solving CSPs using weak local consistency. SIAM J. Comput. 50(4), 1263\u20131286 (2021)","journal-title":"SIAM J. Comput."},{"key":"10091_CR19","unstructured":"Krokhin, A.A., \u017eivn\u00fd, S. (eds.): Editors. The Constraint Satisfaction Problem: Complexity and Approximability. vol. 7 of Dagstuhl Follow-Ups Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"10091_CR20","doi-asserted-by":"crossref","unstructured":"Kun, G., O\u2019donnell, R., Tamaki, S., Yoshida, Y., Zhou, Y.: Linear programming, width-1 csps, and robust satisfaction. In: Goldwasser, S. (ed.) Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pp. 484\u2013495. ACM (2012)","DOI":"10.1145\/2090236.2090274"},{"key":"10091_CR21","doi-asserted-by":"crossref","unstructured":"Meisels, A.: Distributed Search by Constrained Agents - Algorithms, Performance, Communication. Advanced Information and Knowledge Processing. Springer (2008)","DOI":"10.1007\/978-1-84800-040-7"},{"key":"10091_CR22","doi-asserted-by":"crossref","unstructured":"Morris, C., Ritzert, M., Fey, M., Hamilton, W.-L., Lenssen, J.-E., Rattan, G., Grohe, M.: 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, pp. 4602\u20134609. AAAI Press (2019)","DOI":"10.1609\/aaai.v33i01.33014602"},{"key":"10091_CR23","unstructured":"Rossi, F., Van Beek, P., Walsh, T. (eds.): Handbook of constraint programming. Vol. 2 of Foundations of Artificial Intelligence. Elsevier (2006)"},{"key":"10091_CR24","unstructured":"Toenshoff, J., Ritzert, M., Wolf, H., Grohe, M.: RUN-CSP: Unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, abs\/1909.08387 (2019)"},{"key":"10091_CR25","unstructured":"Xu, K., Hu, W., Leskovec, J., Jegelka, S.: 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)"},{"key":"10091_CR26","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Kameda, T.: Computing on an anonymous network. In: Dolev, D. (ed.) Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, Toronto, Ontario, Canada. August 15-17 1988. pp. 117\u2013130. ACM (1988)","DOI":"10.1145\/62546.62568"},{"key":"10091_CR27","unstructured":"Yokoo, M., Durfee, E.H., Ishida. T., Kuwabara, K.: 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. pp. 614\u2013621. IEEE Computer Society (1992)"},{"issue":"5","key":"10091_CR28","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1109\/69.729707","volume":"10","author":"M Yokoo","year":"1998","unstructured":"Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K.: The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Trans. Knowl. Data Eng. 10(5), 673\u2013685 (1998)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"10091_CR29","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1023\/A:1010078712316","volume":"3","author":"M Yokoo","year":"2000","unstructured":"Yokoo, M., Hirayama, K.: Algorithms for distributed constraint satisfaction: A review. Auton. Agents Multi Agent Syst. 3(2), 185\u2013207 (2000)","journal-title":"Auton. Agents Multi Agent Syst."},{"key":"10091_CR30","unstructured":"Zhuk, D.: Berkeley, CA, USA, October 15-17, 2017. pp. 331\u2013342. IEEE, Computer Society. In: Umans, C. (ed.) 58th IEEE Annual symposium on foundations of computer science, FOCS (2017)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10091-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10091-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10091-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:17:09Z","timestamp":1724447829000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10091-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10091"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10091-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,8]]},"assertion":[{"value":"29 May 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}