Verifying Compliance with Commitment Protocols
Tóm tắt
Interaction protocols are specific, often standard, constraints on the behaviors of autonomous agents in a multiagent system. Protocols are essential to the functioning of open systems, such as those that arise in most interesting web applications. A variety of common protocols in negotiation and electronic commerce are best treated as commitment protocols, which are defined, or at least analyzed, in terms of the creation, satisfaction, or manipulation of the commitments among the participating agents. When protocols are employed in open environments, such as the Internet, they must be executed by agents that behave more or less autonomously and whose internal designs are not known. In such settings, therefore, there is a risk that the participating agents may fail to comply with the given protocol. Without a rigorous means to verify compliance, the very idea of protocols for interoperation is subverted. We develop an approach for testing whether the behavior of an agent complies with a commitment protocol. Our approach requires the specification of commitment protocols in temporal logic, and involves a novel way of synthesizing and applying ideas from distributed computing and logics of program.
Tài liệu tham khảo
G. A. Agha and N. Jamali, Concurrent programming for distributed artificial intelligence, in Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, Gerhard Weiss (Ed.), MIT Press, Cambridge, MA, 1998, Chapter 12, pages 505–534.
M. Benerecetti, F. Giunchiglia, and L. Serafini, “Model checking multiagent systems,” Journal of Logic and Computation, vol. 8(3), pp. 401–423, 1998.
K. P. Birman, “The process group approach to reliable distributed computing,” Communications of the ACM, vol. 36(12), pp. 36–53, 1993.
K. P. Birman, “A response to Cheriton and Skeen's criticism of causal and totally ordered communication,” Operating Systems Review, vol. 28(1), pp. 11–21, 1994.
N. Carriero and D. Gelernter, “Coordination languages and their significance,” Communications of the ACM, vol. 35(2), pp. 97–107, 1992.
D. R. Cheriton and D. Skeen, “Understanding the limitations of causally and totally ordered communication,” in Proceedings of the 14th ACM Symposium on Operating System Principles (SOSP), ACM Press, December 1993, pp. 44–57.
L. Chiariglione, “Foundation for intelligent physical agents (FIPA) scope,” 1998. www.fipa.org/library/scope.html.
P. Ciancarini, A. Knoche, R. Tolksdorf, and F. Vitali, “PageSpace: An architecture to coordinate distributed applications on the web,” Computer Networks and ISDN System, 28(7–11), pp. 941–952, 1996. Proceedings of the 5th International World Wide Web Conference.
P. Ciancarini, R. Tolksdorf, F. Vitali, D. Rossi, and A. Knoche, “Coordinating multiagent applications on the WWW: A reference architecture,” IEEE Transactions on Software Engineering, vol. 24(5), pp. 362–375, 1998.
E. A. Emerson, “Temporal and modal logic,” in Handbook of Theoretical Computer Science, Jan van Leeuwen (ed.), North-Holland, Amsterdam, 1990, Volume B, pp. 995–1072.
N. Francez and I. R. Forman, Interacting Processes: A Multiparty Approach to Coordinated Distributed Programming, ACM Press and Addison-Wesley, New York, 1996.
J. Gray and A. Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, San Mateo, 1993.
L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, vol. 21(7), pp. 558–565, 1978.
J. A. Rodríguez-Aguilar, F. J. Martín, P. Noriega, P. Garcia, and C. Sierra, “Towards a test-bed for trading agents in electronic auction markets,” AI Communications, vol. 11(1), pp. 5–19, 1998.
R. Schwarz and F. Mattern, “Detecting causal relationships in distributed computations: In search of the holy grail,” Distributed Computing, vol. 7(3), pp. 149–174, 1994.
M. P. Singh, “Agent communication languages: Rethinking the principles,” IEEE Computer, vol. 31(12), pp. 40–47, 1998.
M. P. Singh, “Applying the mu-calculus in planning and reasoning about action,” Journal of Logic and Computation, vol. 8(3), pp. 425–445, 1998.
M. P. Singh, “A customizable coordination service for autonomous agents,” in Intelligent Agents IV: Proceedings of the 4th International Workshop on Agent Theories, Architectures, and Languages (ATAL-97), Springer-Verlag, 1998, pp. 93–106.
M. P. Singh, “Developing formal specifications to coordinate heterogeneous autonomous agents,” in Proceedings of the 3rd International Conference on Multiagent Systems (ICMAS), IEEE Computer Society Press, July 1998, pp. 261–268.
M. P. Singh, “An ontology for commitments in multiagent systems: Toward a unification of normative concepts,” Artificial Intelligence and Law, 1999. In press.
G. Weiss, Editor, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, MIT Press, Cambridge, MA, 1998.
M. J. Wooldridge, “Verifiable semantics for agent communication languages,” in Proceedings of the 3rd International Conference on Multiagent Systems (ICMAS), IEEE Computer Society Press, July 1998, pp. 349–356.