A Nonmonotonic Soft Concurrent Constraint Language to Model the Negotiation Process

• Autorzy: Bistarelli S. , Santini F.
• Języki publikacji: EN

Abstrakty

EN

We present an extension of the Soft Concurrent Constraint language that allows the nonmonotonic evolution of the constraint store. To accomplish this, we introduce some new operations: retract(c) reduces the current store by c, updateX(c) transactionally relaxes all the constraints of the store that deal with the variables in the set X, and then adds a constraint c; nask(c) tests if c is not entailed by the store. The new retraction operators also permit to reason about Belief Revision, i.e. the process of changing beliefs to take into account a new piece of information. We present this framework as a possible solution to the negotiation of resources (e.g. web services and network resource allocation) that need a given Quality of Service (QoS). For this reason we also show the the new operators of the language satisfy the Belief Revision postulates [20], which can be used in the negotiation process. The QoS requirements (expressed as semiring levels) of all the parties should converge on a formal agreement through a negotiation process, which specifies the contract that must be enforced.

Słowa kluczowe

EN

Soft Constraint Concurrent Programming; Nonmonotonicity; belief revision; quality of service; negotiation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 111, nr 3
• Strony: 257--279
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Bistarelli S.

autor

Santini F.

• Dipartimento di Matematica e Informatica, Universita di Perugia, Via Vanvitelli 1, Perugia, Italy,

Bibliografia

• [1] Alchourron, C. E., Gardenfors, P., Makinson, D.: On the Logic of Theory Change: Partial Meet Contraction and Revision Functions, The Journal of Symbolic Logic, 50(2), 1985, 510-530.
• [2] Baccelli, F., Cohen, G., Olsder, G. J., Quadrat, J.-P.: Synchronization and Linearity: an algebra for discrete event systems, JohnWiley & Sons, 1992.
• [3] Bergstra, J. A.: Handbook of Process Algebra, Elsevier Science Inc., New York, NY, USA, 2001, ISBN 0444828303.
• [4] Best, E., de Boer, F. S., Palamidessi, C.: Partial Order and SOS Semantics for Linear Constraint Programs, COORDINATION '97, Springer-Verlag, 1997, ISBN 3-540-63383-9.
• [5] Bhoj, P., Singhal, S., Chutani, S.: SLA management in federated environments, Comput. Networks, 35(1), 2001, 5-24, ISSN 1389-1286.
• [6] Bistarelli, S., Gabbrielli, M., Meo, M. C., Santini, F.: Timed Soft Concurrent Constraint Programs, COORDINATION' 08 (D. Lea, G. Zavattaro, Eds.), 5052, Springer, 2008, ISBN 978-3-540-68264-6.
• [7] Bistarelli, S., Gadducci, F.: Enhancing Constraints Manipulation in Semiring-Based Formalisms, European Conference on Artificial Intelligence (ECAI), 2006.
• [8] Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint satisfaction and optimization, J. ACM, 44(2), 1997, 201-236, ISSN 0004-5411.
• [9] Bistarelli, S., Montanari, U., Rossi, F.: Soft concurrent constraint programming, ACM Trans. Comput. Logic, 7(3), 2006, 563-589, ISSN 1529-3785.
• [10] Bistarelli, S., Santini, F.: A NonmonotonicSoft ConcurrentConstraint Language for SLA Negotiation, Electr. Notes Theor. Comput. Sci., 236, 2009, 147-162.
• [11] Blyth, T., Janowitz, M.: Residuation Theory, Pergamon press, 1972.
• [12] de Boer, F. S., Kok, J. N., Palamidessi, C., Rutten, J. J. M. M.: Non-monotonic Concurrent Constraint Programming., ILPS, 1993.
• [13] Booth, R., Richter, E.: On Revising Fuzzy Belief Bases, Studia Logica, 80(1), 2005, 29-61.
• [14] Buscemi, M. G., Montanari, U.: CC-Pi: A Constraint-Based Language for Specifying Service Level Agreements, ESOP'07, 4421, Springer, 2007, ISBN 978-3-540-71314-2.
• [15] Codognet, P., Rossi, F.: NMCC Programming: Constraint Enforcement and Retracting in CC Programming, ICLP'95, 1995.
• [16] Cohen, D., Cooper,M., Jeavons, P., Krokhin, A.: The complexity of soft constraint satisfaction, Artif. Intell., 170(11), 2006, 983-1016, ISSN 0004-3702.
• [17] De Nicola, R., Ferrari, G. L., Montanari, U., Pugliese, R., Tuosto, E.: A Process Calculus for QoS-Aware Applications, COORDINATION'95, 3454, Springer, 2005, ISBN 3-540-25630-X.
• [18] Fages, F., Ruet, P., Soliman, S.: Linear concurrent constraint programming: operational and phase semantics, Inf. Comput., 165(1), 2001, 14-41, ISSN 0890-5401.
• [19] Flouris, G., Plexousakis, D., Antoniou, G.: On Generalizing the AGM Postulates, Proceeding of the 2006 conference on STAIRS 2006, IOS Press, Amsterdam, The Netherlands, The Netherlands, 2006, ISBN 1-58603-645-9.
• [20] Gardenfors, P., Ed.: Belief Revision, Cambridge University Press, New York, NY, USA, 1992, ISBN 0521412609.
• [21] Hanemann, A., Schmitz, D., Sailer,M.: A Framework for Failure ImpactAnalysis and Recoverywith Respect to Service Level Agreements, SCC '05: Proceedings of the 2005 IEEE International Conference on Services Computing, IEEE Computer Society, Washington, DC, USA, 2005, ISBN 0-7695-2408-7-02.
• [22] Jennings, N., Faratin, P., Lomuscio, A., Parsons, S., Sierra, C., Wooldridge, M.: Automated negotiation: prospects, methods and challenges, Int Journal of Group Decision and Negotiation, 10(2), 2001, 199-215.
• [23] Keller, A., Ludwig, H.: The WSLA Framework: Specifying and Monitoring Service Level Agreements for Web Services, J. Netw. Syst. Manage., 11(1), 2003, 57-81, ISSN 1064-7570.
• [24] Laprie, J.-C., Randell, B.: Basic Concepts and Taxonomy of Dependable and Secure Computing, IEEE Trans. Dependable Secur. Comput., 1(1), 2004, 11-33, ISSN 1545-5971.
• [25] Martin, K.: Chapter 8. Foundationalism and Coherentism, Knowledge by Agreement, 1(9), 2002, 91-102.
• [26] Saraswat, V., Jagadeesan, R., Gupta, V.: Default timed concurrent constraint programming, POPL '95, ACM Press, 1995, ISBN 0-89791-692-1.
• [27] Saraswat, V., Lincoln, P.: Higher-order Linear Concurrent Constraint Programming, Technical report, Xerox Parc, 1992.
• [28] Saraswat, V., Rinard,M.: Concurrent constraint programming, POPL '90, ACMPress, 1990, ISBN 0-89791-343-4.
• [29] Saraswat, V. A., Jagadeesan, R., Gupta, V.: Default Timed Concurrent Constraint Programming, POPL '95: Proceedings of Principles of Programming Languages, ACM Press, San Francisco, California, January 22-25, 1995.
• [30] Saraswat, V. A., Rinard, M., Panangaden, P.: The semantic foundations of concurrent constraint programming, POPL '91: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM Press, New York, NY, USA, 1991, ISBN 0-89791-419-8.
• [31] Yokoo, M., Durfee, E. H., Ishida, T., Kuwabara, K.: The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, 10(5), 1998, 673-685, ISSN 1041-4347.
• [32] Zhang, D., Foo, N.,Meyer, T., Kwok, R.: Negotiation as mutual belief revision, AAAI'04: Proceedings of the 19th national conference on Artifical intelligence, AAAI Press / TheMIT Press, 2004, ISBN 0-262-51183-5.