Towards design tools for protocol development

ABSTRACT

Interaction protocols enable agents to communicate with each other effectively. Whereas several approaches exist to specify interaction protocols, none of them has design tools that can help protocol designers catch semantical protocol errors at design time. As research in networking protocols has shown, flawed specifications of protocols can have disastrous consequences. Hence, it is crucial to systematically analyze protocols in time to ensure correct specification. This paper studies and formalizes important generic properties of commitment protocols that can ease their correct development significantly. Since these properties are formal, they can easily be incorporated in a software tool to (semi-)automate the design and specification of commitment protocols. Where appropriate we provide algorithms that can directly be used to check these properties in such a design tool.

REFERENCES

• 1: Marco Alberti , Davide Daolio , Paolo Torroni , Marco Gavanelli , Evelina Lamma , Paola Mello, Specification and verification of agent interaction protocols in a logic-based system, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.967918]
• 2: Alexander Artikis , Jeremy Pitt , Marek Sergot, Animated specifications of computational societies, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545070]
• 3: Jamal Bentahar , Bernard Moulin , John-Jules Ch. Meyer , Brahim Chaib-draa, A Logical Model for Commitment and Argument Network for Agent Communication, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.792-799, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.18]
• 4: C. Castelfranchi. Commitments: From individual intentions to groups and organizations. In Proc. of the Intl Conf. on Multiagent Systems, pages 41--48, 1995.
• 5: T. H. Cormen, C. E. Leiserson, and R. Rivest. Design and Analysis of Algorithms. MIT Press, 1990.
• 6: V. Dignum, J.-J. Meyer, F. Dignum, and H. Weigand. Formal specification of interaction in agent societies. In 2nd Goddard Workshop on Formal Approaches to Agent-Based Systems (FAABS), Maryland, Oct 2002.
• 7: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Protocol conformance for logic-based agents. In Proc. of Intl. Joint Conf. on AI (IJCAI), pages 679--684. 2003.
• 8: FIPA. Contract net interaction protocol specification, 2002. Number 00029.
• 9: Nicoletta Fornara , Marco Colombetti, Operational specification of a commitment-based agent communication language, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544868]
• 10: Mohamed G. Gouda, Protocol verification made simple: a tutorial, Computer Networks and ISDN Systems, v.25 n.9, p.969-980, April 1993 [doi>10.1016/0169-7552(93)90094-K]
• 11: Gerard J. Holzmann, Design and validation of computer protocols, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 12: M.-P. Huget and J.-L. Koning. Requirement analysis for interaction protocols. In Proc. of the Central and Eastern European Conf. on Multiagent Systems (CEEMAS), LNAI 2691, pages 404--412. Springer-Verlag, 2003.
• 13: Nicholas R. Jennings, On agent-based software engineering, Artificial Intelligence, v.117 n.2, p.277-296, March 2000 [doi>10.1016/S0004-3702(99)00107-1]
• 14: R Kowalski , M Sergot, A logic-based calculus of events, New Generation Computing, v.4 n.1, p.67-95, 1986 [doi>10.1007/BF03037383]
• 15: A. U. Mallya, P. Yolum, and M. P. Sing. Resolving commitments among autonomous agents. In M.-P. Huget and F. Dignum, editors, Proceedings of the AAMAS Workshop on Agent Communication Languages and Conversation Policies, LNAI 2922, pages 166--182. Springer Verlag, 2003.
• 16: Peter McBurney , Simon Parsons, Posit spaces: a performative model of e-commerce, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860675]
• 17: Murray Shanahan, Solving the frame problem: a mathematical investigation of the common sense law of inertia, MIT Press, Cambridge, MA, 1997
• 18: M. P. Singh. An ontology for commitments in multiagent systems: Toward a unification of normative concepts. Artificial Intelligence and Law, 7:97--113, 1999.
• 19: Mahadevan Venkatraman , Munindar P. Singh, Verifying Compliance with Commitment Protocols, Autonomous Agents and Multi-Agent Systems, v.2 n.3, p.217-236, September 1999 [doi>10.1023/A:1010056221226]
• 20: Pinar Yolum , Munindar P. Singh, Flexible protocol specification and execution: applying event calculus planning using commitments, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 2, July 15-19, 2002, Bologna, Italy [doi>10.1145/544862.544867]
• 21: Pınar Yolum , Munindar P. Singh, Reasoning about Commitments in the Event Calculus: An Approach for Specifying and Executing Protocols, Annals of Mathematics and Artificial Intelligence, v.42 n.1-3, p.227-253, September 2004 [doi>10.1023/B:AMAI.0000034528.55456.d9]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Design, Verification

Keywords:
commitments, protocols, tools