Soft concurrent constraint programming

ABSTRACT

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, as yet there seems to be no concurrent programming framework where soft constraints can be handled. In this article we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many Web-related scenarios. In fact, the language level allows Web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.

REFERENCES

• 1: Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and McManus, J. 1999. Rfc2702: Requirements for traffic engineering over MPLS. Tech. rep. Network Working Group.
• 2: Giampaolo Bella , Stefano Bistarelli, Soft Constraints for Security Protocol Analysis: Confidentiality, Proceedings of the Third International Symposium on Practical Aspects of Declarative Languages, p.108-122, March 11-12, 2001
• 3: Bella, G. and Bistarelli, S. 2002. Confidentiality levels and deliberate/indeliberate protocol attacks. In Proceedings of the 10th Cambridge International Security Protocol Workshop (CISPW2002). Lecture Notes in Computer Science, vol. 2845. Springer, Berlin, Germany, 104--119.
• 4: Bistarelli, S. 2001. Soft constraint solving and programming: A general framework. Ph.D. dissertation. Dipartimento di Informatica, Università di Pisa, Pisa, Italy.
• 5: Stefano Bistarelli , Simon N. Foley, Analysis of Integrity Policies using Soft Constraints, Proceedings of the 4th IEEE International Workshop on Policies for Distributed Systems and Networks, p.77, June 04-06, 2003
• 6: Bistarelli, S. and Foley, S. 2003b. A constraint framework for the qualitative analysis of dependability goals: Integrity. In Proceedings of the 22th International Conference on Computer Safety, Reliability and Security (SAFECOMP2003). Lecture Notes in Computer Science, vol. 2788. Springer, Berlin Germany, 130--143.
• 7: Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint solving over semirings. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI95). Morgan Kaufman, San Francisco, CA, 624--630.
• 8: Stefano Bistarelli , Ugo Montanari , Francesca Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM (JACM), v.44 n.2, p.201-236, March 1997 [doi>10.1145/256303.256306]
• 9: Stefano Bistarelli , Francesca Rossi, Semiring-based contstraint logic programming: syntax and semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.1-29, Jan. 2001 [doi>10.1145/383721.383725]
• 10: Frank S. de Boer , Catuscia Palamidessi, A fully abstract model for concurrent constraint programming, Proceedings of the international joint conference on theory and practice of software development on Colloquium on trees in algebra and programming (CAAP '91): vol 1, p.296-319, April 1991, Brighton, United Kingdom
• 11: Calisti, M. and Faltings, B. 2000. Distributed constrained agents for allocating service demands in multi-provider networks. J. Italian Operat. Res. Soc. Special issue on constraint-based problem solving. XXIX, 91.
• 12: Distributed QoS Routing with Imprecise State Information, Proceedings of the International Conference on Computer Communications and Networks, p.614, October 12-15, 1998
• 13: Clark, D. 1989. Rfc1102: Policy routing in internet protocols. Tech. rep. Network Working Group.
• 14: Frank S. de Boer , Catuscia Palamidessi, From concurrent logic programming to concurrent constraint programming, Advances in logic programming theory, Oxford University Press, Inc., New York, NY, 1995
• 15: De Nicola, R., Ferrari, G., Montanari, U., Pugliese, R., and Tuosto, E. 2003. A formal basis for reasoning on programmable QoS. In Verification---Theory and Practice, N. Dershowitz, Ed. Lecture Notes in Computer Science, vol. 2772. Springer, Berlin, Germany, 436--479.
• 16: Dubois, D., Fargier, H., and Prade, H. 1993. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proceedings of the IEEE International Conference on Fuzzy Systems. IEEE Computer Society Press, Los Alamitos, CA, 1131--1136.
• 17: Hélène Fargier , Jérôme Lang, Uncertainty in Constraint Satisfaction Problems: a Probalistic Approach, Proceedings of the European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, p.97-104, November 08-10, 1993
• 18: Eugene C. Freuder , Richard J. Wallace, Partial constraint satisfaction, Artificial Intelligence, v.58 n.1-3, p.21-70, Dec. 1992 [doi>10.1016/0004-3702(92)90004-H ]
• 19: Jain, R. and Sun, W. 2000. QoS/policy/constraintnbased routing. In Carrier IP Telephony 2000 Comprehensive Report. International Engineering Consortium, Chicago, IL.
• 20: Rocco de Nicola , Gian Luigi Ferrari , Rosario Pugliese, KLAIM: A Kernel Language for Agents Interaction and Mobility, IEEE Transactions on Software Engineering, v.24 n.5, p.315-330, May 1998 [doi>10.1109/32.685256 ]
• 21: Plotkin, G. 1981. Post-graduate lecture notes in advanced domain theory (incorporating the Pisa lecture notes). Technical rep. Department of Computer Science, University of Edinburgh, Edinbur, Scotland.
• 22: Ruttkay, Z. 1994. Fuzzy constraint satisfaction. In Proceedings of the 3rd IEEE International Conference on Fuzzy Systems. 1263--1268.
• 23: Vijay A. Saraswat, Concurrent constraint programming, MIT Press, Cambridge, MA, 1993
• 24: Vijay A. Saraswat , Martin Rinard , Prakash Panangaden, The semantic foundations of concurrent constraint programming, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-352, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99627]
• 25: Thomas Schiex, Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, Proceedings of the eighth conference on Uncertainty in Artificial Intelligence, p.268-275, June 1992, Stanford, California, United States
• 26: Schiex, T., Fargier, H., and Verfaille, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI95). Morgan Kaufmann, San Francisco, CA, 631--637.
• 27: Dana S. Scott, Domains for Denotational Semantics, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.577-613, July 12-16, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics; Syntax
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages; Constraint and logic languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures; Constraints

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

Keywords:
Constraints, concurrent constraint programming, soft constraints