An asynchronous, message-efficient, distributed algorithm for enforcing partial consistency in information networks

Antonopoulou, Hera; Papadopoulos, Dimitris; Stamatiou, Yannis C.

doi:10.47974/JDMSC-2583

Open Access Research Article

An asynchronous, message-efficient, distributed algorithm for enforcing partial consistency in information networks

^*Hera AntonopoulouCorresponding authorhera@upatras.grDepartment of Management Science and Technology University of PatrasPatras, 26334, Greece0000-0002-3936-435XView full profile → , Dimitris Papadopoulosdimfpap@upatras.grDepartment of Management Science and Technology University of PatrasPatras, 26334, Greece0000-0002-0725-3954View full profile → , Yannis C. Stamatioustamatiu@upatras.grDepartment of Business Administration University of Patras; Computer Technology Institute and Press - DiophantusDepartment of Business Administration University of PatrasPatras, 26504, Greece0000-0002-8925-9427View full profile →

* Corresponding author · click or hover a name for details

pp. 1365–1379Vol. 29Issue 3March 2026DOI: 10.47974/JDMSC-2583 Crossmark XML

Received:: 12 Feb 2025
Published Online:: 02 Mar 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2583
Pages:: 1365–1379

Abstract

In this work we present a totally asynchronous distributed algorithm for the problem of achieving arc-consistency in a network of constraints. The algorithm is designed for multicomputer systems. Since the number and size of messages are two factors of major concern when solving a problem distributively we have paid particular attention to designing the algorithm in a way that tends to reduce their number and size. Our approach relies on identifying whether a message can be suppressed without affecting the operation of the process to which it was addressed. This has the effect of keeping the number of exchanged messages low at a cost of some small extra computation time.

Keywords

Constraint satisfaction Arc-consistency Parallel computation Asynchronous algorithms Distributed computation Multiprocessors

Subject Classifications

68W15

References

[1] H. Antonopoulou, “A user authentication protocol based on the intractability of the 3-coloring problem”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 5, no. 1, pp. 17–21 (2002).
[2] H. Antonopoulou, “On threshold properties”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 7, no. 2, pp. 249–254 (2004).
[3] S. Antonopoulou, Y.C. Stamatiou, and M. Vamvakari, “An asymptotic expansion for the q-binomial series using singularity analysis for generating functions”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 10, no. 3, pp. 313–328 (2007).
[4] H. Antonopoulou, N. Glinos, and Y.C. Stamatiou, “An identity derived from the solution of a class of differential equations for the evolution of a key agreement protocol”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 14, no. 6, pp. 515–520 (2011).
[5] H. Antonopoulou, “Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 23, no. 7, pp. 1431–1438 (2020).
[6] K. R. Apt, “The essence of constraint propagation”, Theoretical Computer Science, vol. 221, pp. 179-210 (1999).
[7] K. R. Apt, Principles of Constraint Programming. Cambridge University Press (2003).
[8] D.A. Cohen, M.C. Cooper, and P.G. Jeavons, “Characterizing tractable constraints”, Artificial Intelligence, vol. 65, pp. 347–361 (1994).
[9] D. Conforti, L. Grandinetti, R. Musmanno, M. Cannataro, G. Spezzano, and D. Talia, “A model of efficient asynchronous parallel algorithms on multicomputer systems”, Parallel Computing, vol. 18, pp. 31–45 (1992).
[10] P.R. Cooper and M.J. Swain, “Arc consistency: parallelism and domain dependence”, Artificial Intelligence, vol. 58, pp. 207–235 (1992).
[11] R. Dechter, “Constraint networks”, in Encyclopedia of Artificial Intelligence, Second Edition, S. Shapiro Ed., New York, Wiley, pp. 276–285 (1992).
[12] R. Dechter and I. Meiri, “Experimental evaluation of preprocessing algorithms for constraint satisfaction problems”, Artificial Intelligence, vol. 68, pp. 211–241 (1994).
[13] E.C. Freuder and D. Sabin, “Contradicting Conventional Wisdom in Constraint Satisfaction”, in Proceedings of the Second Workshop on Principles and Practice of Constraint Programming, pp. 10–20 (1994).
[14] P. Van Hentenryck, Y. Deville, and C.-M. Teng, “A generic arc-consistency algorithm and its specializations”, Artificial Intelligence, vol. 57, pp. 291–321 (1992).
[15] R.M. Karp and V. Ramachandran, “Parallel algorithms for shared-memory machines”, in Handbook of Theoretical Computer Science, J. van Leeuwen, ed., Amsterdam: Elsevier (1990).
[16] S. Kasif, “On the parallel complexity of discrete relaxation in constraint satisfaction networks”, Artificial Intelligence, vol. 45, pp. 275–286 (1990).
[17] S. Kasif and A.L. Delcher, “Local consistency in parallel constraint satisfaction networks”, Artificial Intelligence, vol. 69, pp. 307–327 (1994).
[18] L.M. Kirousis, “Fast parallel constraint satisfaction”, Artificial Intelligence, vol. 64, pp. 147–160 (1993).
[19] S. C. Kleene, Introduction to Metamathematics. D. Van Nostrand, Princeton, 1952. Reprinted by North-Holland, Amsterdam, 1952. Dover, New York (2002).
[20] A.K. Mackworth, “Constraint satisfaction”, in: Encyclopedia of Artificial Intelligence, S. Shapiro Ed., New York, Wiley, pp. 285–293 (1992).
[21] A.K. Mackworth and E.C. Freuder, “The complexity of some polynomial network consistency algorithms for constraint satisfaction problems”, Artificial Intelligence, vol. 25, pp. 65–74 (1985).
[22] A.K. Mackworth and E.C. Freuder, “The complexity of constraint satisfaction revisited”, Artificial Intelligence, vol. 59, pp. 57–62 (1993).
[23] F. Mattern, “Algorithms for Distributed Termination Detection”, Distributed Computing, vol. 2, pp. 161–175 (1987).
[24] R. Mohr and T.C. Henderson, “Arc and Path Consistency Revisited”, Artificial Intelligence, vol. 28, pp. 225–233 (1986).
[25] A. Samal and T.C. Henderson, “Parallel consistent labeling algorithms”, International Journal of Parallel Programming, vol. 16, no. 5, pp. 341–364 (1987).
[26] A. Tarski, “A lattice-theoretical fixpoint theorem and its applications”, Pacific Journal of Mathematics, vol. 5, no. 2, pp. 285-309 (1955).
[27] S. Taylor, Parallel Logic Programming Techniques, Prentice-Hall (1989).
[28] Y. Zhang and A.K. Mackworth, “Parallel and distributed algorithms for finite constraint satisfaction problems”, in Proceedings of 3rd IEEE Symposium on Parallel and Distributed Processing, Dallas, TX, pp. 394–397 (1991).

Views: 46Downloads: 8Citations: 0