Reliable group communication and virtual synchrony in multiagent systems

In the last few years agents and multiagent systems have been strongly investigated by researcher communities all over the world because of the strong contribute and the great potential on software engineering and artificial intelligence fields. Since then, platforms and agent communication languages (ACLs) have been deployed in order to create environments where agents could be developed and implemented and in order to make agents interact with each other. Agent standardization has been carried out mostly by FIPA (Foundation for Intelligent Physical Agents) that introduced agent standards, from agent abstract architecture to transport protocols, from communicative acts to agent communication languages. This work will mainly focus on agent communication, mostly on reliable group communication. FIPA ACLs consider only one-to-one interactions, they have not been designed for group communication purposes. However, we strongly believe that group interactions can be a milestone in agent societies as it is in human societies. For instance, teachers can talk to a wide audience of students (as a group) in a classroom; in the same way agents should be able to consider their message recipients not only as single entities, but as a group of entities as well. Starting from previous works on group communication, we argue that group communication should be a complement to standard one-to-one interaction, rather than the only solution. We propose different forms of group interactions, considering agents as entities that (as humans do) have the freedom to choose the communication that better fits their needs. Different scenarios require different ways of transferring information, that is, in human societies face-to-face meetings are not the same as phone calls. In agent societies a similar argument should be supported. Moving from our belief that agents should be able to choose their way to communicate, we argue that more on group communication should be done than standard asynchronous communication. Some scenario would certainly need stronger guarantees than the ones that can be achieved through an asynchronous infrastructure. We propose a virtually synchronous architecture, where group members receive joining and leaving members on their message queues as well as the same set of group messages between views. We introduce some new group semantics, we describe how an ACL message should be modified in order to support group interactions and we provide an architecture where agents can interact in a group oriented fashion. Jade is a broadly used, FIPA compliant agent platform; we choose it as a base for our group oriented architecture. Even though it does not include any group capabilities, it provides an excellent plug-in service, which on one hand is really poorly documented (at least at the time this thesis work has been carried out), but on the other hand (once its features have been discovered) it makes quite easy for developers to design and implement a new service.UnpublishedP. Busetta, A. Donà, and M. Nori. Channeled multicast for group communication. In Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2002), pages 1280-1287. ACM Press, 2002. K. P. Birman and T. A. Joseph. Reliable communication in the presence of failures. ACM Transaction on Computer Systems, 5(1):47-76, 1987. B. Chaib-Draa and G. Dignum. Trends in Agent Communication Language. Computational Intelligence, 18(2), pp.89-101, 2002. S. Cranefield. Reliable group communication and institutional action in a multi-agent trading scenario. AAMAS 2005, 1119-1120. D. R. Cheriton and D. Skeen. Undertanding the limitations of casually and totally ordered communication. Operating Systems Review, 27(5):44-57,1993. (Proceedings of the 4th ACM Symposium on Operating Systems Principles). H. van Ditmarsch. Some game theory of Pit. In C. Zhang, H. W. Guesgen, and W. Yeap, editors, Proceedings of the 8th Pacific Rim International Conference on Artificial Intelligence, volume 3157 of Lecture Notes In Artificial Intelligence, pages 946-947. Springer, 2004. F. Dignum and G. Vreeswijk. Towards a testbed for multi-party dialogues. In M.-P. Huget and F. Dignum, editors, AAMAS 2003 Workshop on Agent Communication Language and Conversation Policies (ACL 2003), Melbourne, 2003, July 2003. E. Emerson and J. Halpern. “Sometimes” and “not never” revisited: On branching versus linear temporal logic. Journal of the ACM, 33(1):151-178,1986. Foundation for Intelligent Physical Agent. FIPA ACL Message Structure Specification, 2002. Document number SC00061G. http://www.fipa.org. Foundation for Intelligent Physical Agent. FIPA Communicative Act Library Specification, 2002. Document number SC00037J. http://www.fipa.org. Foundation for Intelligent Physical Agents. FIPA English Auction Interaction Protocol Specification, 2002. Document number XC00031F. http://www.fipa.org. R. Fagin, J. Y. Halpern, Y.Moses, and M. Y. Vardi. Reasoning about knowledge. MIT press, Cambridge, MA, 1995. FIPA project home page. http://www.fipa.org. Marc-Philippe Huget, Yves Demazeau: First Steps Towards Multi-party Communication. AC 2004: 65-75. Ip Multicast HOWTO. http://www.tldp.org/HOWTO/Multicast-HOWTO.html. JADE project home page. http://jade.tilab.com, 2005. Java Project home page. http://java.sun.com. JGroups project home page. http://www.jgroups.org, 2004. Project JXTA home page. http://www.jxta.org. Sanjeev Kumar, Marcus J. Huber, David R. McGee, Philip R. Cohen, and Hector J. Levesque. Semantics of Agent Communication Languages for Group Interaction. In Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI'00), American Association for Artificial Intelligence Press, Austin, Texas, July 30-August 3, 2000, pages 42-47. KQLM project home page. http://www.cs.umbc.edu/kqml/. R. J. Lipton. How to cheat at mental poker. Computer Science Dept., Berkeley, CA, August 1979. Nowostawski, M., Purvis, M., and Cranefield, S., KEA, Multi-level Agent Infrastracture, Published, in Proceedings of the 2nd International Workshop of Central and Eastern Europe on Multi-Agent Systems (CEEMAS 2001) University of Mining and Metallurgy, Krakow, Poland pp.355-362 (2001), http://www.sf.net/projects/javaprs. G. Neiger, and S. Toueg. Simulating synchronized clocks and common knowledge in distributed systems. Journal of the ACM, 40(2):334-367, 1993. Object Management Group. UML 2.0 superstructure final adopted specification. Document ptc/03-08-02, http://www.omg.org/cgi-bin/doc?ptc/2003-08-02, 2003. S. Paurobally, J. Cunningham, and N. R. Jennings. Ensuring consistency in the joint beliefs of interactiong agents. In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2003), pages 662-669. ACM Press, 2003. Purvis, M., Cranefield, S.,Nowostawski, M., and Carter, D., “Opal: A Multi-Level Infrastructure for Agent-Oriented Software Development”, Information Science Discussion Paper Series, No. 2002/01, ISSN 1172-6024, University of Otago, Dunedin, New Zealand. Pit Game, Parker Bros., Inc., Salem, MA (1904) see http://centralconnector.com/GAMES/pit.html. M. Purvis, M. Nowostawsky, S. Cranefield, and M.Oliveira. Multi-agent interaction technology for peer-to-peer computing in electronic trading environments. In C. Zhang, H. W. Guesgen, and W. Yeap, editors, Proceedings of the 8th Pacific Rim International Conference on Artificial Intelligence, volume 3157 of Lecture Notes In Artificial Intelligence, pages 625-634. Springer, 2004. P. Panangaden, K. Taylor, Concurrent Common Knowledge: Defining Agreement for Asynchronous Systems, Distributed Computing, Vol. 6, pp. 73-93, 1992. RFC 1700 Assigned Numbers. http://www.faqs.org/rfcs/rfc1700.html. A. Shamir, L. Rivest, L.Adleman. A Method for Obtaining Digital Signature and Public-Key Cryptosystems, in Communications of the ACM 21,2 (February 1978), pp.120-126. C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27, 1948. A. Shamir, L. Rivest, L.Adleman. Mental Poker. MIT Technical Report, 1978. A. S. Tanenbaum, M. van Steen. Distributed Systems : Principles and Paradigms, Prentice Hal, 2002. A. S. Tanenbaum, M. van Steen. Distributed Systems : Principles and Paradigms, Prentice Hal, 2002. Telecom Italia Lab home page. http://www.telecomitalialab.com D. Traum. Issues in multiparty dialogues. In F. Dignum, editor, Advances in Agent Communication, number 2922 in Lecture Notes in Computer Science, pages 201-211. Springer-Verlag, 2003. M. Wooldridge and N. R. Jennings. Intelligent agents: Theory and practice. Knowledge Engineering review, 10(2):115-152,1995