On illegal composition of first-class agent interaction protocols

ABSTRACT

In this paper, we examine the composition of first-class protocols for multi-agent systems. First-class protocols are protocols that exist as executable specifications that agents use at runtime to acquire the rules of the protocol. This is in contrast to the standard approach of hard-coding interaction protocols directly into agents --- an approach that seems too restrictive for many intelligent and adaptive agents. In previous work, we have proposed a framework called RASA, which regards protocols as first-class entities. RASA includes a formal, executable language for multi-agent protocol specification, which, in addition to specifying the order of messages using a process algebra, also allows designers to specify the rules and consequences of protocols using constraints. Rather than having hard-coded decision making mechanisms for choosing their next move, agents can inspect the protocol specification at runtime to do so. Such an approach would allow the agents to compose protocols at runtime, instead of relying on statically designed protocols. In this paper, we investigate the implications of protocol composition by examining the conditions under which composing existing legal protocols would lead to illegal protocols --- that is, protocols that can fail during execution through no fault of the participants. We precisely define what constitutes an illegal protocol, and present proof obligations about compositions that, when discharged, demonstrate that a composition is legal.

REFERENCES

• 1: A. Bloesch and O. Traynor. The Cogito tool architecture. Technical Report 95-7, Software Verification Research Centre, 1995.
• 2: Frank S. De Boer , Maurizio Gabbrielli , Elena Marchiori , Catuscia Palamidessi, Proving concurrent constraint programs correct, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.685-725, Sept. 1997 [doi>10.1145/265943.265954]
• 3: L. P. de Silva, M. Winikoff, and W. Liu. Extending agents by transmitting protocols in open systems. In Proceedings of the Challenges in Open Agent Systems Workshop, Melbourne, Australia, 2003.
• 4: N. Desai, A. U. Mallya, A. K. Chopra, and M. P. Singh. OWL-P: A methodology for business process modeling and enactment. In Workshop on Agent Oriented Information Systems, pages 50--57, July 2005.
• 5: N. Desai and M. P. Singh. A modular action description language for protocol composition. In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI), pages 962--967. AAAI Press, 2007.
• 6: Paul E. Dunne, Prevarication in dispute protocols, Proceedings of the 9th international conference on Artificial intelligence and law, June 24-28, 2003, Scotland, United Kingdom [doi>10.1145/1047788.1047791]
• 7: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 8: J. McGinnis and T. Miller. Amongst first-class protocols. In Engineering Societies in the Agents World VIII, LNAI, 2007. (To Appear).
• 9: T. Miller and P. McBurney. Executable logic for reasoning and annotation of first-class interaction protocols. Technical Report ULCS-07-015, University of Liverpool, Department of Computer Science, 2007.
• 10: T. Miller and P. McBurney. Using constraints and process algebra for specification of first-class agent interaction protocols. In G. O'Hare, A. Ricci, M. O'Grady, and O. Dikenelli, editors, Engineering Societies in the Agents World VII, volume 4457 of LNAI, pages 245--264, 2007.
• 11: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 12: D. Robertson. Multi-agent coordination as distributed logic programming. In Proceedings of the International Conference on Logic Programming, volume 3132 of LNCS, pages 416--430. Springer, 2004.
• 13: S. Schneider. The B-Method: An Introduction. Palgrave, 2001.
• 14: J. M. Spivey, The Z notation: a reference manual, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1992
• 15: 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

Keywords:
interaction protocols, multi-agent systems